【基础练习】【强连通tarjan】codevs1332 上白沢慧音题解

小咪咪 2022-08-09 09:44 109阅读 0赞

题目描述 Description

在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。

输入描述 Input Description

第1行：两个正整数N,M

第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。

输出描述 Output Description

第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。

第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。

样例输入 Sample Input

5 5

1 2 1

1 3 2

2 4 2

5 1 2

3 5 1

样例输出 Sample Output

1 3 5

数据范围及提示 Data Size & Hint

对于60%的数据：N <= 200且M <= 10,000

对于100%的数据：N <= 5,000且M <= 50,000

基础tarjan 先做一遍缩点 在每次出栈时统计每个强连通分量包含的点数以及最小的点的编号（因为一个点只会出现在一个强连通分量=scc中，包含点数相同的情况下字典序最小的scc就是最小的点的编号最小的那个scc），最后把目标scc从vector转移到数组中 排序并输出

这次又犯了几个低级错误 一个是把=达成了== 原来一直是把==打成= 这次竟然相反了= =

还有很重要的一个错误是，调试时发现tarjan找到小环就直接退栈了，并没有找最大的环。和原来代码对比才发现，当时的错误代码是：

for (int i=head[k];i!=0;i=next[i])
        {
            if (!dfn[to[i]])//还没有tarjan过 
            {
                tarjan(to[i]);
                low[k]=min(low[to[i]],low[k]);
            }
            else if (ins[to[i]])//如果tarjan过且在栈中说明是祖先，如果不在栈中说明是横叉边 
            {
                low[k]=min(low[to[i]],low[k]); 
            }
    	if (dfn[k]==low[k])
            {
                tot++;
                int j,mi=0x3f3f3f;
                do
                {
                    cnt[tot]++;
                    j=sta[stp--];
                    ins[j]=false;
                    scc[tot].push_back(j);
                    if (j<mi) mi=j;
                }
                while (j!=k);
                if (cnt[tot]>big) big=cnt[tot];
                first[tot]=mi;
            }
        }

而正解代码应该是：

for (int i=head[k];i!=0;i=next[i])
        {
            if (!dfn[to[i]])//还没有tarjan过 
            {
                tarjan(to[i]);
                low[k]=min(low[to[i]],low[k]);
            }
            else if (ins[to[i]])//如果tarjan过且在栈中说明是祖先，如果不在栈中说明是横叉边 
            {
                low[k]=min(low[to[i]],low[k]); 
            }
        }
        if (dfn[k]==low[k])
        {
            tot++;
            int j,mi=0x3f3f3f;
            do
            {
                cnt[tot]++;
                j=sta[stp--];
                ins[j]=false;
                scc[tot].push_back(j);
                if (j<mi) mi=j;
            }
            while (j!=k);
            if (cnt[tot]>big) big=cnt[tot];
            first[tot]=mi;
        }

发现有什么不同了吗？

对了，退栈过程的位置不一样！这会带来什么呢？

原来，我们之所以要循环完毕再退栈而不是找到祖先就退栈，就是为了防止找到小环直接退栈而忽略了大环存在的情况。

如果我们把退栈过程放在循环内部，那么每当程序找到一个k的祖先x更新low\[k\]后，**不满足条件dfn\[k\]==low\[k\]就会直接退出子程序**，退到上一层或几层递归，到达祖先节点x那层时 祖先节点必然满足dfn\[k\]==low\[k\]，这时对于这个小环就会理所当然地出栈处理。

而我们应当注意的是，**找到k的祖先x后，有可能k还有其他出边，通向新的子节点，实际形成的强连通分量可能会更大，而实际的low\[k\]会更小。**

如果我们把k的所有出边循环一遍的话，当我们检验当前节点是否满足low\[k\]==dfn\[k\]时，当前节点能找到的所有点都已经遍历过了，因此**如果先找到了祖先会暂时忽视，优先向深处查找更多的点**。当满足dfn\[k\]==low\[k\]时，必然有要么搜到了叶子节点，要么除了祖先其他节点都已访问完毕，也就是该节点下面的子树已经完全遍历了，此时再更新low\[k\]时，得到的low\[k\]一定是最大环中当前节点所能追溯到的最早祖先（但注意同一强连通分量中low不一定相同，我们在上一篇抢掠计划题解中已经证明），而当low\[k\]==dfn\[k\]时所有同一强连通分量中的点必然都在栈中，此时出栈得到的就是最大环的点了。

这个程序也再一次证明了

else if (ins[to[i]])//如果tarjan过且在栈中说明是祖先，如果不在栈中说明是横叉边 
            {
                low[k]=min(low[to[i]],low[k]); 
            }

在这里，更新时写成low\[to\[i\]\]或者dfn\[to\[i\]\]并没有影响。

那么这道题目的代码如下：

//codevs1332 上白沢慧音 tarjan
    //copyright by ametake
    //task：求出每个scc并记录每个scc包含的节点个数和编号 最后输出最大的scc包含结点个数和编号 只输出一个字典序最小的恶 
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    using namespace std;
    
    const int maxn=5000+10;
    const int maxm=50000+10;
    int n,m;
    int head[maxn],to[maxm*2],next[maxm*2],et=0;
    int dfn[maxn],low[maxn],sta[maxn],dep=0,stp=0;
    bool ins[maxn];
    vector
           
             scc[maxn]; int cnt[maxn],tot=0; int final[maxn],first[maxn]; int big=0,num=0; inline void add(int &x,int &y) { et++; to[et]=y; next[et]=head[x]; head[x]=et; } inline int read() { int f=1,a=0; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { a=a*10+ch-'0'; ch=getchar(); } a*=f; return a; } void tarjan(int k) { dfn[k]=low[k]=++dep; sta[++stp]=k; ins[k]=true; for (int i=head[k];i!=0;i=next[i]) { if (!dfn[to[i]])//还没有tarjan过 { tarjan(to[i]); low[k]=min(low[to[i]],low[k]); } else if (ins[to[i]])//如果tarjan过且在栈中说明是祖先，如果不在栈中说明是横叉边 { low[k]=min(low[to[i]],low[k]); } } if (dfn[k]==low[k]) { tot++; int j,mi=0x3f3f3f; do { cnt[tot]++; j=sta[stp--]; ins[j]=false; scc[tot].push_back(j); if (j
            
             big) big=cnt[tot]; first[tot]=mi; } } void output() { int mi=0x3f3f3f,best; for (int i=1;i<=tot;i++) { if (cnt[i]==big) { if (first[i]

`——若为化得身千亿，散上峰头望故乡。`