1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
| 裸的tarjan。可是我有个问题
不知道是数据太水还是我理解错了，我用一个没比字典序的程序竟然AC了，（这说明数据没有多种最大的的，我认为字典序输出是输出字典序小的 ，不是吗？ ）
下面是加字典序的代码
#include<cstdio>
#include<iostream>
using namespace std;
int n,m;
const int M=200000;
int head[M],to[M],nex[M];//数组模拟链表
int tot;
int vis[M];
int zhan[M];
int t[M],s[M];
void add(int x,int y)//添加临接点
{
nex[++tot]=head[x];
to[tot]=y;
head[x]=tot;
}
int num;
int col[M];
int dfn[M];
int low[M];
int top;
int numc;
void tarjan(int x)
{
dfn[x]=++num;
low[x]=num;
vis[x]=1;
zhan[++top]=x;
for(int i=head[x];i;i=nex[i])//枚举临接点
{
int tmp=to[i];
if(!dfn[tmp])
{
tarjan(tmp);
low[x]=min(low[x],low[tmp]);
}
else
{
if(vis[tmp]) low[x]=min(low[x],dfn[tmp]);
}
}
if(low[x]==dfn[x])
{
numc++;
while(zhan[top]!=x)//如果栈顶不为x出栈
{
vis[zhan[top]]=0;
col[zhan[top]]=numc;
t[numc]++;//强联通分量中有几个点
s[numc]=min(numc,zhan[top]);//每个强联通分量找最小的
top--;
}
vis[x]=0;
top--;
col[x]=numc;
t[numc]++;
s[numc]=min(x,s[numc]);// x出栈
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
add(x,y);
if(c==2) add(y,x);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
int max1=-1;
int z;
for(int i=1;i<=numc;i++)
{
if(t[i]>max1) max1=t[i],z=i;//找点最多的强联通分量记录下来编号
}
for(int i=1;i<=numc;i++)
{
if(t[i]==max1&&s[i]<s[z])z=i;//找字典序最小的
}
printf("%d\n",t[z]); //输出编号
for(int i=1;i<=n;i++)
if(col[i]==z)
printf("%d ",i);//输出
return 0;
}
|
