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

虽然AC了,但是782MS,求大神指教,怎么样才能减少时间(附代码)

Posted by 201293123 at 2013-03-23 15:57:19 on Problem 2492
#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:
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