P1726 上白泽慧音

提交 8.40k
通过 4.05k
时间限制 1.00s
内存限制 125.00MB
题目提供者 yeszy
历史分数100

提交记录

查看题解

标签

 
查看算法标签
进入讨论版

相关讨论

 
查看讨论

推荐题目

 
查看推荐
 

展开

题目描述

在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由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

 

思路

　　对于所有强连通分量染上同一种颜色，统计出最大的颜色群，对于最早出现的点的颜色属于最大颜色群时记录该颜色。

　　输出该颜色的强连通分量。

　　dfs的话可以用set输出，不过想了想好像for更好

CODE

 

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 
  4 using namespace std;
  5 typedef long long LL;
  6 const int maxn = 1e5 + 7;
  7 
  8 int head[maxn], dfn[maxn], low[maxn], st[maxn];
  9 int cnt = 0, tot = 0, tim = 0, top = 1, n, cl = 0, m, mx = 0;
 10 int vis[maxn];
 11 int color[maxn];
 12 int ans[maxn];
 13 int nxt[maxn];
 14 int circle_size[maxn];
 15 
 16 /*
 17 head[],结构体edge:存边
 18 
 19 dfn[],low[]:tarjan中数组
 20 
 21 st[]:模拟栈
 22 
 23 out[]:出边
 24 
 25 sd[]:强连通分量存储
 26 
 27 dq[]:统计答案
 28 */
 29 
 30 set<int> s;
 31 
 32 template<class T>inline void read(T &res)
 33 {
 34     char c;T flag=1;
 35     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 36     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 37 }
 38 
 39 struct Edge{
 40     int nxt, to;
 41 }edge[maxn * 2];
 42 
 43 inline void BuildGraph(int from, int to)
 44 {
 45     cnt++;
 46     edge[cnt].to = to;
 47     edge[cnt].nxt = head[from];
 48     head[from] = cnt;
 49 }
 50 
 51 void tarjan(int x)
 52 {
 53     tim++;
 54     dfn[x] = low[x] = tim;
 55     st[top] = x;
 56     top++;
 57     vis[x] = 1;
 58     for(int i = head[x] ; i != 0; i = edge[i].nxt)
 59     {
 60         int u = edge[i].to;
 61         if(vis[u] == 0)
 62         {
 63             tarjan(u);
 64             low[x]=min(low[x],low[u]);
 65         }
 66         else if(vis[u] == 1)
 67                 low[x]=min(low[x],dfn[u]);
 68     }
 69     if(dfn[x] == low[x])
 70     {
 71         cl++;
 72         do
 73         {
 74             top--;
 75             color[st[top]] = cl;
 76             vis[st[top]] = -1;
 77         }while( st[top] != x );
 78     }
 79     return ;
 80 }
 81 
 82 void dfs(int u, int step, int fa) {
 83     if(step == mx) {
 84         return;
 85     }
 86     for (int i = head[u]; i; i = nxt[i]) {
 87         int v = edge[i].to;
 88         if(v == fa || color[v] != color[u])
 89             continue;
 90         else {
 91             s.insert(v);
 92             dfs(v, step + 1, u);
 93         }
 94     }
 95 }
 96 
 97 int main()
 98 {
 99     scanf("%d %d",&n, &m);
100     int opt;
101     for ( int i = 1; i <= m; ++i ) {
102         int u, v;
103         scanf("%d %d %d",&u, &v, &opt);
104         if(opt == 1) {
105             BuildGraph(u, v);
106         }
107         else if(opt == 2) {
108             BuildGraph(u, v);
109             BuildGraph(v, u);
110         }
111         //ans[i] = 1;
112     }
113     for ( int i = 1; i <= n; ++i ) {
114         if( !vis[i] ) {
115             tarjan(i);
116         }
117     }
118     for ( int i = 1; i <= n; ++i) {
119         circle_size[color[i]]++;
120         mx = max(mx, circle_size[color[i]]);
121     }
122     for ( int i = 1; i <= n; ++i ) {
123         //printf("color[%d]:%d\n",i,color[i]);
124     }
125     cout << mx << endl;
126     int temp = 0;
127     for ( int i = 1; i <= n; ++i ) {
128         if(circle_size[color[i]] == mx) {
129             temp = i;
130             s.insert(temp);
131         }
132         if(temp != 0) {
133             for ( int j = 1; j <= n; ++j ) {
134                 if(color[j] == color[temp]) {
135                     s.insert(j);
136                 }
137             }
138             set<int>::iterator it;
139             for (it = s.begin(); it != s.end(); it++) {
140                 cout << *it << " ";
141             }
142             puts("");
143             break;
144         }
145     }
146     return 0;
147 }
View Code