# _ **~~Tarjan了解一下?~~** _
by little_sun @ 2018-06-01 20:09:13
@[Fraciton](/space/show?uid=32107)
by little_sun @ 2018-06-01 20:09:25
我很久以前写过[blog](https://www.cnblogs.com/cjjsb/p/8137581.html)
by hl666 @ 2018-06-01 20:23:20
@[Fraciton](/space/show?uid=32107) 其实我还是觉得Tarjan更好
不过我记得刘汝佳的蓝书上有的
by hl666 @ 2018-06-01 20:24:34
@[hl666](/space/show?uid=41698) 我知道，比起Tarjan，我对Kosaraju这种魔性做法更感兴趣
by Fraction @ 2018-06-01 20:30:00
@[hl666](/space/show?uid=41698) 您博客中的一些地方我有些不懂，请问您能够把源代码发给我吗？
by Fraction @ 2018-06-01 20:48:17
```
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=5005;
vector <int> a[N],b[N],s;
int f[N],i,n,m,x,y,z,ans,num,c[N],tot,t[N];
inline void read(int &x)
{
x=0; char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline void dfs(int k)
{
f[k]=0;
for (int i=0;i<a[k].size();++i)
if (f[a[k][i]]) dfs(a[k][i]);
s.push_back(k);
}
inline void rdfs(int k)
{
f[k]=0;
c[k]=tot;
t[tot]++;
for (int i=0;i<b[k].size();++i)
if (f[b[k][i]]) rdfs(b[k][i]);
}
int main()
{
read(n); read(m);
for (i=1;i<=m;++i)
{
read(x); read(y); read(z);
if (z==1)
{
a[x].push_back(y);
b[y].push_back(x);
} else
{
a[x].push_back(y); a[y].push_back(x);
b[x].push_back(y); b[y].push_back(x);
}
}
memset(f,true,sizeof(f));
for (i=1;i<=n;++i)
if (f[i]) dfs(i);
memset(f,true,sizeof(f));
for (i=s.size()-1;i;--i)
if (f[s[i]]) ++tot,rdfs(s[i]);
for (i=1;i<=tot;++i)
if (t[i]>ans) ans=t[i],num=i;
printf("%d\n",ans);
for (i=1;i<=n;++i)
if (c[i]==num) printf("%d ",i);
return 0;
}
```
by hl666 @ 2018-06-01 23:43:58
这是一道强连通分量的板子题[Luogu P1726 上白泽慧音](https://www.luogu.org/problemnew/show/P1726)的CODE
by hl666 @ 2018-06-01 23:45:28
@[Fraciton](/space/show?uid=32107) 这是很久以前写的了，码风有点**惊奇**请不要介意
by hl666 @ 2018-06-01 23:46:51
@[hl666](/space/show?uid=41698) 好的谢谢
by Fraction @ 2018-06-02 10:18:47