题解 P1726 【上白泽慧音】

· · 题解

裸的一道强连通分量题，对于向我们这种萌新练手很不错，练习tarjan。像我这种lowb就用的最弱的vector存储法，还是过了。手写下栈吧还是，毕竟又不是什么优先队列没必要用stl，反而不方便。我看大家都没有讲tarjan算法啊，我还是讲讲吧（主要是想之后不会写的时候再看看）

tarjan其实很简单，dfn存储搜到的时间，low存储搜到的最早的点，我们对这个图进行构建dfs树，搜到一个点就入栈，当你的dfn==low的时候，以这个点往下建的子树，并且还在栈里的都会在这个强连通分量里，因为强连通分量不会有重叠，所以每个点就只会入一次，而且每次找到的强连通分量必定已经包含了所有点。具体可以去网上搜搜。

这道题就单独开两个变量，一个存当前最大的强连通分量有多少个点，另一个就存当前的有多少个，如果更多就更新。如果一样就比下最小的就行了，最后把那个强连同分量的从小到大输出就行，具体见代码

#include<bits/stdc++.h>
using namespace std;
#define MAX 5000
int c[MAX+10],vis[MAX+10]={0},dfn[MAX+10],low[MAX+10],huan[MAX+10],maxn=0,ltfl=0,mini=100000,mini2=100000;//ltfl=连通分量= =存的哪一个连通分量，c 是否在栈中，vis是否搜过，dfn搜到时间，low他能去到的最早时间，huan在哪个环中，maxn强连通分量中最多有多少个点，mini当前最大强连通分量中最小点，mini2目前搜到的强连通分量最小的点 
int sta[MAX+10],head=0,t=0;//栈    
int n,m;
vector<int>load[50000+10];
void tarjan(int now)
{
    dfn[now]=low[now]=++t;//初始化每一个第一次进搜到的点 
    vis[now]=1;
    int x=load[now].size();
    sta[head++]=now;
    c[now]=1;
    for(int i=0;i<x;i++)//搜图 
    {
        if(vis[load[now][i]]==0)
        {
            tarjan(load[now][i]);
            low[now]=min(low[now],low[load[now][i]]);//他的子树能到达，他也能的 
        }
        else if(c[load[now][i]]==1)
        {
            low[now]=min(low[now],dfn[load[now][i]]);//如果这是一条后向边，那就直接看是否是能到的最小的 
        }
    }
    if(dfn[now]==low[now])
        {
            int y=0;
            mini=100000;
            while(1)
            {
                head--;
                int v=sta[head];
                y++; 
                huan[v]=low[now];
                if(v<mini)
                {
                    mini=v;
                }
                c[v]=0;
                //printf("%d ",v);
                if(now==v)
                {
                //    printf("\n");
                    if(y>maxn)
                    {
                        maxn=y;
                        ltfl=low[now];
                        mini2=mini;
                    }
                    if(y==maxn)
                    {
                        if(mini<mini2)
                        {
                            mini2=mini;
                            ltfl=low[now];
                        }
                    } 
                    break;
                }
            }
        }    
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,l;
        scanf("%d %d %d",&x,&y,&l);
        load[x].push_back(y);
        if(l==2)
        {
            load[y].push_back(x);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        tarjan(i);
    }
    printf("%d\n",maxn);
    for(int i=1;i<=n;i++)
    {
        if(huan[i]==ltfl)
        {
            printf("%d ",i);
        }
    }
}