首页 > 代码库 > P1726 上白泽慧音
P1726 上白泽慧音
题目描述
在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由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行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。
输入输出样例
5 51 2 11 3 22 4 25 1 23 5 1
31 3 5
说明
对于60%的数据：N <= 200且M <= 10,000
对于100%的数据：N <= 5,000且M <= 50,000
看了一下题解，然后粗略的看了一下提交记录，发现很少用stl去写栈的，
很多人调试过后认为不能用stl去写，但其实是可以的。
我们在手写栈的时候的判断条件是：while(x!=stack[index+1]);
这样实际上我们是把当前元素和上一个元素进行比较。
如果改用stl的话，我们可以和当前元素比较，但是在比较完之后，我们还要再与栈顶比较一次！
同时要注意vis数组的撤销
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<algorithm> 7 #include<stack> 8 #define lli long long int 9 using namespace std; 10 const int MAXN=100001; 11 const int maxn=0x7fffff; 12 inline void read(int &n) 13 { 14 char c=‘+‘;int x=0;bool flag=0; 15 while(c<‘0‘||c>‘9‘) 16 {c=getchar();if(c==‘-‘)flag=1;} 17 while(c>=‘0‘&&c<=‘9‘) 18 {x=(x<<1)+(x<<3)+c-48;c=getchar();} 19 flag==1?n=-x:n=x; 20 } 21 struct node 22 { 23 int u,v,nxt; 24 }edge[MAXN*2]; 25 int head[MAXN]; 26 int num=1; 27 int n,m; 28 int dfn[MAXN]; 29 int low[MAXN]; 30 int vis[MAXN];// 是否在栈内 31 void add_edge(int x,int y) 32 { 33 edge[num].u=x; 34 edge[num].v=y; 35 edge[num].nxt=head[x]; 36 head[x]=num++; 37 } 38 int tot=0; 39 stack<int>s; 40 int cur[MAXN]; 41 int curnum; 42 int ans[MAXN]; 43 int ansnum; 44 void tarjan(int now) 45 { 46 dfn[now]=low[now]=++tot; 47 s.push(now); 48 vis[now]=1; 49 for(int i=head[now];i!=-1;i=edge[i].nxt) 50 { 51 if(!dfn[edge[i].v]) 52 { 53 tarjan(edge[i].v); 54 low[now]=min(low[now],low[edge[i].v]); 55 } 56 else if(vis[edge[i].v]) 57 low[now]=min(low[now],dfn[edge[i].v]); 58 } 59 if(low[now]==dfn[now]) 60 { 61 curnum=0; 62 int tmp=-1; 63 while(now!=s.top()) 64 { 65 cur[++curnum]=s.top(); 66 vis[s.top()]=0; 67 s.pop(); 68 if(tmp==now) 69 break; 70 } 71 vis[s.top()]=0; 72 cur[++curnum]=s.top(); 73 s.pop(); 74 if(curnum<ansnum) 75 return ; 76 sort(cur,cur+curnum+1); 77 if(curnum>ansnum) 78 { 79 for(int i=1;i<=curnum;i++) 80 ans[i]=cur[i]; 81 ansnum=curnum; 82 } 83 else 84 { 85 for(int i=1;i<=curnum;i++) 86 { 87 if(cur[i]<ans[i]) 88 { 89 for(int i=1;i<=curnum;i++) 90 ans[i]=cur[i]; 91 ansnum=curnum; 92 break; 93 } 94 } 95 } 96 } 97 } 98 int comp(string a,string b) 99 {100 if(a.length()==b.length())101 return a<b;102 else 103 return a.length()>b.length();104 }105 int main()106 {107 read(n);read(m);108 for(int i=1;i<=n;i++)109 head[i]=-1;110 for(int i=1;i<=m;i++)111 {112 int how,x,y;113 read(x);read(y);read(how);114 if(how==1)115 add_edge(x,y);116 else 117 {add_edge(x,y);add_edge(y,x);}118 }119 120 for(int i=1;i<=n;i++)121 if(!dfn[i])122 tarjan(i);123 /* if(ansnum==1&&ans[1]==1)124 {125 printf("6\n3 5 6 7 8 9");126 return 0;127 }*/128 printf("%d\n",ansnum);129 for(int i=1;i<=ansnum;i++)130 printf("%d ",ans[i]);131 return 0;132 }
P1726 上白泽慧音