这显然是一道求强连通分量(SCC)的题目。
只要你正常,都知道应该写Tarjan。
然后(假装会写Tarjan),其实我当然不会。但是求SCC还有另一个算法。复杂度和Tarjan一样,只不过常数大了点而且不为人所知而已。
蓝书和挑战程序竞赛上都有这个算法,好像叫Kosaraju。是不是很拽的感觉。
具体的算法可以参照我的博客另一篇文章。重点是这道题就是SCC模板题(不敢相信竟然10分钟一次A了)
CODE
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=;
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=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
inline void dfs(int k)
{
f[k]=;
for (int i=;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]=;
c[k]=tot;
t[tot]++;
for (int i=;i<b[k].size();++i)
if (f[b[k][i]]) rdfs(b[k][i]);
}
int main()
{
read(n); read(m);
for (i=;i<=m;++i)
{
read(x); read(y); read(z);
if (z==)
{
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=;i<=n;++i)
if (f[i]) dfs(i);
memset(f,true,sizeof(f));
for (i=s.size()-;i;--i)
if (f[s[i]]) ++tot,rdfs(s[i]);
for (i=;i<=tot;++i)
if (t[i]>ans) ans=t[i],num=i;
printf("%d\n",ans);
for (i=;i<=n;++i)
if (c[i]==num) printf("%d ",i);
return ;
}