| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
虽然AC了,但是782MS,求大神指教,怎么样才能减少时间(附代码)#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
int father[2010];
int rank[2010];
void make_set(int i)
{
father[i]=i;
rank[i]=0;
}
int find(int i)
{
if(father[i]!=i)
{
int t=father[i];
father[i]=find(father[i]);
rank[i]=(rank[i]+rank[t])%2;
}
return father[i];
}
int lu(int m,int n)
{
int rootm,rootn;
rootm=find(m);
rootn=find(n);
father[rootm]=rootn;
rank[rootm]=(2-rank[m]+1+rank[n])%2;
return 0;
}
int main()
{
int N;
int i,j;
int m,n;
int bug1,bug2;
scanf("%d",&N);
for(j=0;j<N;j++)
{
int flag=1;
scanf("%d %d",&m,&n);
for(i=1;i<=m;i++)
{
make_set(i);
}
for(i=0;i<n;i++)
{
scanf("%d %d",&bug1,&bug2);
if(flag==1)
{
int tpm,tpn;
tpm=find(bug1);
tpn=find(bug2);
if(tpm==tpn)
{
if(rank[bug1]==rank[bug2])
flag=0;
}
else
lu(bug1,bug2);
}
}
printf("Scenario #%d:\n",j+1);
if(flag==0)
{
printf("Suspicious bugs found!\n");
}
else{printf("No suspicious bugs found!\n");}
printf("\n");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator