文章目錄

Attack the NEET Princess
Time Limit: 9000MS Memory Limit: 65536KB 64bit IO Format: %lld & %llu
Submit

Status

Description
Houraisan Kaguya (蓬萊山輝夜) is the NEET (not in education, employment or training) princess living in Eientei (永遠亭). She is an unemployed geek, who sits at home and surfs the Internet all day. But today is different, as the Hakurei Shrine Reitaisai Festival (博麗神社例大祭) will be hosted in Hakurei Shrine, Kaguya decides to go to buy some new doujin games.

Fujiwara no Mokou (藤原妹紅) detests Kaguya, and has been planing to attack her for a long time. But she nerver got the chance before because Kaguya kept staying in Eientei, under the protection of Yagokoro Eirin (八意永琳). Knowing that Kaguya will go outside today, Mokou decides to wait on certain road and attack her once she passes there. Mokou don’t know which path Kaguya will choose, but she thinks that there always exits some roads where she can always meet Kaguya.

Input
There are multiple cases. Each case begins with two integers 2 ≤ n ≤ 10000 — the number of villages and 2 ≤ m ≤ 100000 — the number of roads. Then m lines, each contains two integers a and b (0 ≤ a, b < n), indicating a road connecting village a and village b. Village 0 is Eientei and Village n-1 is Hakurei Shrine. They are always connected by roads. There may be more than one roads between two villages.

Output
Find out the roads where Mokou can always meet Kaguya. For each case, output the number of roads in the first line, then output the numbers of the roads in ascending order in the second line.

Sample Input
3 2
0 1
1 2

7 8
0 1
0 2
1 3
2 3
3 4
3 5
4 6
5 6

Sample Output
2
0 1
0

无向图找桥,再筛选一下桥,筛选的时候,注意到新的图变成了一棵树,因此遍历一次树即可,不需要回溯

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const int N=10010;
const int M=100010;

struct EDGE
{
    int v,next,i;
};
EDGE edge[M*2],edge2[M*2];
bool vis[N];

int first[N],low[N],dfn[N],belong[N],degree[N],sta[M],instack[M],first2[N];
int g,cnt,top,scc,g2;
int min(int a,int b)
{
    return a<b?a:b;
}
void AddEdge(int u,int v)
{
    edge[g].v=v;
    edge[g].next=first[u];
    first[u]=g++;
}
void AddEdge2(int u,int v,int i)
{
    edge2[g2].v=v;
    edge2[g2].i=i;
    edge2[g2].next=first2[u];
    first2[u]=g2++;
}
void Tarjan(int u,int fa)
{
    int i,v;
    low[u]=dfn[u]=++cnt;
    sta[++top]=u;
    instack[u]=1;
    for(i=first[u];i!=-1;i=edge[i].next)
    {
        v=edge[i].v;
        if(i==(fa^1))
            continue;
        if(!dfn[v])
        {
            Tarjan(v,i);
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        scc++;
        while(1)
        {
            v=sta[top--];
            instack[v]=0;
            belong[v]=scc;
            if(v==u)
                break;
        }
    }
}

int que[M];
int rear = 0;
void output(int a){
    que[rear++] = a;
}

int n,m;
bool dfs(int u,int fa){
    int i,v;
    vis[u] = true;
    if (u == belong[n])
        return true;
    for(i=first2[u];i!=-1;i=edge2[i].next)
    {
        //printf("%d\n",i);
        v=edge2[i].v;
        if (vis[v])
            continue;
        if(i==(fa^1))
            continue;
        if (dfs(v,i)){
            output(edge2[i].i);
            return true;
        }
    }
    return false;
}

int _edge[M][2];

int main()
{
    int u,v,i;
    while (~scanf("%d%d",&n,&m)){
        g=cnt=top=scc=0;
        memset(first,-1,sizeof(first));
        memset(low,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        memset(instack,0,sizeof(instack));
        memset(degree,0,sizeof(degree));
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            {
                u ++;
                v ++;
                _edge[i][0] = u;
                _edge[i][1] = v;
                AddEdge(u,v);
                AddEdge(v,u);
            }
        }
        for(i=1;i<=n;i++)
            if(!dfn[i])
                Tarjan(i,-1);

        //printf("DEBUG %d\n",scc);
        memset(first2,-1,sizeof(first2));
        g2 = 0;
        for (i=0;i<m;i++){
            int u = belong[_edge[i][0]];
            int v = belong[_edge[i][1]];
            AddEdge2(u,v,i);
            AddEdge2(v,u,i);
        }
        memset(vis,0,sizeof vis);
        rear = 0;
        dfs(belong[1],-1);

        sort(que,que+rear);
        printf("%d\n",rear);
        //if (rear > 0)
        {
            for (i=0;i<rear;i++){
                printf("%d",que[i]);
                if (i < rear-1)
                    printf(" ");
            }
            printf("\n");
        }
    }
    /*
       for(i=1;i<=n;i++)
       {
       for(j=first[i];j!=-1;j=edge[j].next)
       {
       v=edge[j].v;
       if(belong[i]!=belong[v])
       degree[belong[i]]++;
       }
       }
       int sum=0; for(i=1;i<=n;i++)
       if(degree[i]==1)
       sum++;
       int ans=(sum+1)/2;
       printf("%d\n",ans);
     */
    return 0;
}
文章目錄