#include<stdio.h>
#include<algorithm>
using namespace std;
int dfn[500000],low[500000],stack[900000],j,number,n,m,x,y,w,hh[600000],cnt,top,c,q,ans,yy[100000];
int color[400000],u,num,p[400000];
bool d[500000];
struct node
{
 int next,z,e;
}b[110000];
void add(int aa,int bb)
{
 b[++cnt].e=bb;
 b[cnt].next=hh[aa];
 hh[aa]=cnt;   
}
int tarjan(int k)
{
  int i;
  dfn[k]=low[k]=++number;
  stack[++top]=k;
  d[k]=true;
  for(i=hh[k];i!=0;i=b[i].next)   
  {
      if(!dfn[b[i].e]){
       tarjan(b[i].e);
       low[k]=min(low[k],low[b[i].e]);   
      }
     else if(d[b[i].e]==true)
     {
      low[k]=min(low[k],dfn[b[i].e]);
     }
  }
     if(dfn[k]==low[k])
     {
      color[k]=++num;
      d[k]=false;
      p[num]++;
      while(stack[top]!=k)
      {
       p[num]++;
       color[stack[top]]=num;
       d[stack[top--]]=false;
      }
      top--;
     }
  return 0;
}
int main()
{
 int i;
 scanf("%d %d",&n,&m);
 u=1;
 for(i=1;i<=m;i++)
 {
  scanf("%d %d %d",&x,&y,&w);
  if(w==1)add(x,y);
  else{
      add(x,y);add(y,x);
  }
 }
 for(j=1;j<=n;j++)
 {
  if(!dfn[j])tarjan(j);
 }
 for(i=1;i<=n;i++)
 {
  if(p[color[i]]>ans)ans=p[color[i]],u=i;   
 }
 printf("%d\n",ans);
 for(i=1;i<=n;i++)
 {
  if(color[i]==color[u])printf("%d ",i);
 }
 
 return 0;
 
 
 
 
}
以上是ac代码   但我原本tarjan里写的是
if(dfn[k]==low[k])
     {
      color[k]=++num;
      while(1)
      {
       p[num]++;
       d[top]=false;
       color[stack[top--]]=num;
       if(stack[top+1]==k)break;
      }
     }
十个点全错了，求解释两段代码难道有什么不一样吗，没看出来

[此贴子已经被作者于2016-9-13 11:29编辑过]

这道题是codevs 1332上白泽慧音

人家的taran函数写了20多行，您的作品只有78行，你确定在功能上你们是等价的？

我百度了一下“codevs 1332上白泽慧音”（下次提问希望你能直接给个链接或者把题目发上来），发现有很多博客都已经分享了这道题。相信你自己有能力理解这个题目的题意，也有自己的思路了。
我只问一个细节

for(i=1;i<=n;i++)

 {
  if(color[i]==color[u])printf("%d ",i);

 }

所以这样做出来的输出，最后肯定是会多出一个空格来的。而我本人练习过的平台从来没有哪个平台是可以接受行末有多余空格的。

http://←_←挂上原题链接

那个没有问题，我的问题只是弹栈的那段代码，两种不同的写法一种能过一种不能过
还有我并没有找到博客分享这道题，能给我链接吗

[此贴子已经被作者于2016-9-13 11:18编辑过]

你说的能AC的代码我复制运行结果居然


是我搞错什么了吗？

对不起，我粘错了，已改正，现在可以ac了

我已经发现错误了，谢谢

我看了一下这道题，  基于条件“保证每条道路只出现一次。”，所以对于任意两个村庄a<->b==1就绝对不会存在b<->a==1能令a<->==2,所以所有没有绝对联通的道路是可以忽略不考虑的。
其次，这是一个最大子集的问题。你可以先初始化一个大小为N的数组Node[1~N]，并初始化每一个结点的集合为他们本身即Node【i】=i,然后每读入一组a-b==2就令a,b两个结点所在集合合并成一个更大的集合（通常是取编号较小的那个结点作为该集合的代表）{考虑两种情况：1.if（Node【a】==a,Node[b]==b）{Node[a]=Node[b]=Min(a,b)}else{比较复杂一点，遍历整个数组，找出所有Node[i]==(Node[a]||Node[b]){重置Node[i]=Min(Node[a],Node[b])}}}
读完M组数据以后只要遍历整个数组，找到那个出现频率最高的集合输出就行了。

两种都调至ac了
d[top]  改成dp[stack[top]]就a了（犯了个愚蠢的错误）