在幻想乡,上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞,使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由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。
输入格式:
第1行:两个正整数N,M
第2..M+1行:每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路,t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。
输出格式:
第1行: 1个整数,表示最大的绝对连通区域包含的村庄个数。
第2行:若干个整数,依次输出最大的绝对连通区域所包含的村庄编号。
输入样例#1:
5 5
1 2 1
1 3 2
2 4 2
5 1 2
3 5 1
输出样例#1:
3
1 3 5
对于60%的数据:N <= 200且M <= 10,000
对于100%的数据:N <= 5,000且M <= 50,000
不会tarjan于是除了第一个点WA其他都超时,,
不做了。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 using namespace std;
8 const int MAXN=5001;
9 void read(int &n)
10 {
11 char c='+';int x=0;bool flag=0;
12 while(c<'0'||c>'9')
13 {c=getchar();if(c=='-')flag=1;}
14 while(c>='0'&&c<='9')
15 {x=x*10+c-48;c=getchar();}
16 flag==1?n=-x:n=x;
17 }
18 struct node
19 {
20 int u,v,w,nxt;
21 }edge[MAXN*4];
22 int head[MAXN];
23 int num=1;
24 void add_edge(int x,int y,int z)
25 {
26 edge[num].u=x;
27 edge[num].v=y;
28 edge[num].w=z;
29 edge[num].nxt=head[x];
30 head[x]=num++;
31 }
32 bool have[MAXN][MAXN];
33 int pre[MAXN];
34 int nex[MAXN];
35 int out[MAXN];
36 void cler()
37 {
38 memset(have,0,sizeof(have));
39 memset(pre,-1,sizeof(pre));
40 memset(nex,-1,sizeof(nex));
41 }
42 int ans=0;
43 int ansbg=0;
44 int n,m;
45 void calc_ans(int bg,int ed)
46 {
47 int num=0;
48 int hh=ed;
49 while(pre[ed]!=-1)
50 {
51 num++;
52 ed=pre[ed];
53 }
54 num+=1;
55 if(num>ans)
56 {
57 ans=num;
58 ansbg=bg;
59 for(int i=0;i<=n;i++)
60 out[i]=nex[i];
61 }
62 }
63 void dfs(int bg,int now)
64 {
65 for(int i=head[now];i!=-1;i=edge[i].nxt)
66 {
67 if(!have[now][edge[i].v])
68 {
69 if(edge[i].v==bg)
70 {
71 calc_ans(bg,now);
72 return ;
73 }
74 have[now][edge[i].v]=1;
75 have[edge[i].v][now]=1;
76 pre[edge[i].v]=now;
77 nex[now]=edge[i].v;
78 dfs(bg,edge[i].v);
79 have[now][edge[i].v]=0;
80 have[edge[i].v][now]=0;
81 pre[edge[i].v]=-1;
82 nex[now]=-1;
83 }
84 }
85 }
86 int main()
87 {
88
89 read(n);read(m);
90 for(int i=1;i<=n;i++)
91 head[i]=-1;
92 for(int i=1;i<=m;i++)
93 {
94 int x,y,how;
95 read(x);read(y);read(how);
96 if(how==1) add_edge(x,y,1);
97 else {add_edge(x,y,1);add_edge(y,x,1);}
98 }
99 for(int i=1;i<=n;i++)
100 {
101 cler();
102 dfs(i,i);
103 }
104 printf("%d\n",ans);
105 if(ansbg)
106 printf("%d ",ansbg);
107 while(out[ansbg]!=-1)
108 {
109 ansbg=out[ansbg];
110 printf("%d ",ansbg);
111 }
112 return 0;
113 }