Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

人生第二次TARJAN,发帖,纪念哈!

Posted by wzf990404 at 2013-05-16 21:23:17 on Problem 1236
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int ctc,id,n,m,top,st[101],ctd1[101],ctd2[101],dfn[101],low[101],ist[101],ict[101];
vector<int> gr[101];
vector<int> ct[101];
void tarjan(int i)
{int j,k;
 dfn[i]=low[i]=id++;
 ist[i]=1;
 st[++top]=i;
 for(k=0;k<gr[i].size();k++)
 {j=gr[i][k];
  if(dfn[j]==-1)
  {tarjan(j);
   low[i]=min(low[i],low[j]);
  }
  else if(ist[j]) low[i]=min(low[i],dfn[j]);
 }
 if(low[i]==dfn[i])
 {ctc++;
  do
  {j=st[top--];
   ist[j]=0;
   ict[j]=ctc;
   ct[ctc].push_back(j);
  }while(j!=i);
 }
}
int main()
{freopen("poj1236.in","r",stdin);
 freopen("poj1236.out","w",stdout);
 int i,j,ans1=0,ans2=0,k;
 cin>>n;
 for(i=1;i<=n;i++)
  while(scanf("%d",&j)&&j!=0)
   gr[i].push_back(j);
 memset(dfn,-1,sizeof(dfn));
 memset(low,-1,sizeof(low));
 for(i=1;i<=n;i++) if(dfn[i]==-1) tarjan(i);
 for(i=1;i<=n;i++)
  for(k=0;k<gr[i].size();k++)
  {j=gr[i][k];
   if(ict[i]!=ict[j])
   {ctd1[ict[j]]++;
    ctd2[ict[i]]++;
   }
  }
 for(i=1;i<=ctc;i++){ans1+=!ctd1[i];ans2+=!ctd2[i];}
 cout<<ans1<<endl<<(ctc==1?0:max(ans1,ans2));
 return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator