80分tarjan代码求助
查看原帖
80分tarjan代码求助
355092
lynn10楼主2021/8/20 10:02

代码略长,我的思路全注释好了,请各位大佬帮我查错。

#include<cctype>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10001;
int queue[N],head[N],rehead[N],dfn[N],low[N],stack[N],ori[N],out[N],num[N];
//queue用来存储连通分量的“根”如样例1中queue[1] = 3,queue[2] = 1;
//ori用来缩点,如ori[x] = y,表示点x可以合并在连通分量y中;out表示出度,num用来表示连通分量中点的个数
bool vis[N];
int idx,idy,top,tim,n,m,cnt;//tim时间戳,cnt连通分量计数器
struct cow
{
    int u,v,next;
}edge[N * 5],ed[N * 5];
int rd()
{
    int s = 0 , f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-')
        f = - 1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return f * s;
}
void write(int x)
{
    if(x < 0)
    {
        putchar('-');
        x = - x;
    }
    if(x > 9)
    write(x / 10);
    putchar(x % 10 + '0');
}
void add(int u,int v)
{
    edge[++idx].u = u;
    edge[idx].v = v;
    edge[idx].next = head[u];
    head[u] = idx;
}
void readd(int u,int v)
{
    ed[++idy].u = u;
    ed[idy].v = v;
    ed[idy].next = rehead[u];
    rehead[u] = idy;
}
void tarjan(int x)
{
    dfn[x] = low[x] = ++tim;
    stack[++ top] = x;
    vis[x] = 1;
    for(int i = head[x] ; i ; i = edge[i].next)
    {
        int y = edge[i].v;
        if(!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x],low[y]);
        }
        else if(dfn[y] && vis[y])
        {
            low[x] = min(low[x],low[y]);
        }
    }
    if(dfn[x] == low[x])
    {
        int y;
        cnt ++;
        while(y = stack[top --])
        {
            queue[cnt] = x;//将连通量的“根”x记录下来
            ori[y] = x;//y可以合并在为连通分量x中
            vis[y] = 0;//出栈
            num[x] ++;//连通分量x中的点的数量+1
            if(x == y)//到“根”时退出
            break;
            
        }
    }
}
int main()
{
    n = rd(),m = rd();
    for(int i = 1 ; i <= m; i ++)
    {
        int u = rd(),v = rd();
        add(u,v);
    }
    for(int i = 1 ; i <= n ; i ++)
    if(!dfn[i])
    tarjan(i);
    for(int i = 1 ; i <= n ; i ++)//重新建图
    {
        int eu = ori[edge[i].u],ev = ori[edge[i].v];
        if(eu != ev)
        {
            readd(eu,ev);
        }
    }
    for(int i = 1 ; i <= idy ;  i ++)//枚举每一条边
    {
        int u = ed[i].u,v = ed[i].v;//取此边的初、始点;
        out[u]++;//记录出度
    }
    int ans;
    bool flag;
    for(int i = 1 ; i <= cnt ; i ++)//枚举每一个连通分量
    {
        int j = queue[i];//取连通分量的“根”
        if(!out[j])//没有出度
        {
            if(!flag)//是第一个没有出度
            {
                ans = j;//记录答案分量
                flag = 1;//标记答案已饱和
            }
            else//答案过量,不符题意
            {
                return printf("0"),0;
            }
        }
    }
    write(num[ans]);//输出分量中的点数
}

再次感谢各位大佬!!

2021/8/20 10:02
加载中...