P1726 上白泽慧音
2018-06-17 22:14:36来源:未知 阅读 ()
题目描述
在幻想乡,上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞,使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由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 5 1 2 1 1 3 2 2 4 2 5 1 2 3 5 1
3 1 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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:STL—对象的构造与析构
- P1358 扑克牌 2020-05-06
- 博弈--巴什博弈 2020-04-24
- Z 字形变换 2020-04-14
- [题记-并查集] 合根植物 - 蓝桥杯 2020-04-07
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash