首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >P1726 上白泽慧音

P1726 上白泽慧音

作者头像
attack
发布2018-04-12 14:17:59
4900
发布2018-04-12 14:17:59
举报

题目描述

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

看了一下题解,然后粗略的看了一下提交记录,发现很少用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 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-07-10 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 输入输出格式
  • 输入输出样例
  • 说明
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档