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

## 一次ac，贴代码留念一下

Posted by HH_YT at 2012-08-12 10:22:29 on Problem 3207
```#include<stdio.h>
#include<string.h>
int n,m;
int node[1001][1001];
int wire[501][2];
int index;
int cnt;
int stack[1001];
int snum;
int instack[1001];
int belong[1001];
int low[1001];
int DFN[1001];
int tarjan(int n)
{
stack[++snum]=n;
instack[n]=1;
low[n]=DFN[n]=++index;
for(int i=1;i<=node[n][0];i++)
{
if(!DFN[node[n][i]])
{
tarjan(node[n][i]);
if(low[node[n][i]]<low[n])
low[n]=low[node[n][i]];
}
else if(instack[node[n][i]]&&DFN[node[n][i]]<low[n])
{
low[n]=DFN[node[n][i]];
}
}
if(low[n]==DFN[n])
{
cnt++;
while(stack[snum]!=n)
{
belong[stack[snum]]=cnt;
snum--;
}
belong[n]=cnt;
snum--;
}
return 0;
}
int main()
{
int i,j;
int a,b;
int z;
int sum;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=2*m;i++)
node[i][0]=0;
for(i=1;i<=m;i++)
{
scanf("%d%d",&wire[i][0],&wire[i][1]);
}
for(i=1;i<=m;i++)
for(j=i+1;j<=m;j++)
{
if(wire[i][0]>wire[i][1])
{
a=wire[i][1];
b=wire[i][0];
}
else
{
a=wire[i][0];
b=wire[i][1];
}
sum=0;
for(z=0;z<=1;z++)
{
if(wire[j][z]>a&&wire[j][z]<b)
sum++;
}
if(sum==1)
{
node[i][++node[i][0]]=j+m;
node[i+m][++node[i+m][0]]=j;
node[j][++node[j][0]]=i+m;
node[j+m][++node[j+m][0]]=i;
}
}
memset(DFN+1,0,sizeof(int)*m*2);
cnt=0;
index=0;
snum=0;
memset(instack,0,sizeof(instack));
for(i=1;i<=2*m;i++)
{
if(!DFN[i])
tarjan(i);
}
int flag=0;
for(i=1;i<=m;i++)
{
if(belong[i]==belong[i+m])
{
flag=1;
break;
}
}
if(flag)
printf("the evil panda is lying again\n");
else
printf("panda is telling the truth...\n");
}
return 0;
}```

Followed by: