2013年省赛I题 Thrall’s Dream

2013年省赛I题
判断单向联通，用bfs
剪枝：从小到大跑，如果遇到之前跑过的点（也就是编号小于当前点的点），就o(n)传递关系。

bfs

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<ctime>

 #include<set>

 #include<map>

 #include<stack>

 #include<cstring>

 #define inf 2147483647

 #define ls rt<<1

 #define rs rt<<1|1

 #define lson ls,nl,mid,l,r

 #define rson rs,mid+1,nr,l,r

 #define N 100010

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define p(a) putchar(a)

 #define g() getchar()

 using namespace std;

 int T;

 int n,m,cnt;

 int x,y;

 bool b[][];

 struct node{

     int n;

     node *next;

 }*e[];

 queue<int>q;

 void in(int &x){

     int y=;

     char c=g();x=;

     while(c<''||c>''){

         if(c=='-')y=-;

         c=g();

     }

     while(c<=''&&c>=''){

         x=(x<<)+(x<<)+c-'';c=g();

     }

     x*=y;

 }

 void o(int x){

     if(x<){

         p('-');

         x=-x;

     }

     if(x>)o(x/);

     p(x%+'');

 }

 void push(int x,int y){

     node *p;

     p=new node();

     p->n=y;

     if(!e[x])

         e[x]=p;

     else{

         p->next=e[x]->next;

         e[x]->next=p;

     }

 }

 void bfs(int x){

     q.push(x);

     while(!q.empty()){

         int t=q.front();

         q.pop();

         if(t<x){

             For(i,,n)

                 if(b[t][i])

                     b[x][i]=;

         }

         else{

             for(node *i=e[t];i;i=i->next)

                 if(!b[x][i->n]){

                     b[x][i->n]=;

                     q.push(i->n);

                 }

         }

     }

 }

 bool judge(){

     For(i,,n)

         For(j,i+,n)

             if(!b[i][j]&&!b[j][i])

                 return ;

     return ;

 }

 void clear(){

     memset(b,,sizeof(b));

     For(i,,)

         e[i]=;

 }

 int main(){

     in(T);

     while(T--){

         clear();

         in(n);in(m);

         For(i,,m){

             in(x);in(y);

             push(x,y);

         }

         For(i,,n)

             bfs(i);

         printf("Case %d: ",++cnt);

         if(judge())

             printf("Kalimdor is just ahead\n");

         else

             printf("The Burning Shadow consume us all\n");

     }

     return ;

 }

dfs更好写，队友比赛的时候不知道为啥T了

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<ctime>

 #include<set>

 #include<map>

 #include<stack>

 #include<cstring>

 #define inf 2147483647

 #define ls rt<<1

 #define rs rt<<1|1

 #define lson ls,nl,mid,l,r

 #define rson rs,mid+1,nr,l,r

 #define N 100010

 #define For(i,a,b) for(int i=a;i<=b;i++)

 #define p(a) putchar(a)

 #define g() getchar()

 using namespace std;

 int T;

 int n,m,cnt;

 int x,y;

 bool b[][];

 struct node{

     int n;

     node *next;

 }*e[];

 queue<int>q;

 void in(int &x){

     int y=;

     char c=g();x=;

     while(c<''||c>''){

         if(c=='-')y=-;

         c=g();

     }

     while(c<=''&&c>=''){

         x=(x<<)+(x<<)+c-'';c=g();

     }

     x*=y;

 }

 void o(int x){

     if(x<){

         p('-');

         x=-x;

     }

     if(x>)o(x/);

     p(x%+'');

 }

 void push(int x,int y){

     node *p;

     p=new node();

     p->n=y;

     if(e[x]==NULL)

         e[x]=p;

     else{

         p->next=e[x]->next;

         e[x]->next=p;

     }

 }

 // void bfs(int x){

 //     q.push(x);

 //     while(!q.empty()){

 //         int t=q.front();

 //         q.pop();

 //         if(t<x){

 //             For(i,1,n)

 //                 if(b[t][i])

 //                     b[x][i]=1;

 //         }

 //         else{

 //             for(node *i=e[t];i;i=i->next)

 //                 if(!b[x][i->n]){

 //                     b[x][i->n]=1;

 //                     q.push(i->n);

 //                 }

 //         }

 //     }

 // }

 void dfs(int x,int f){

     for(node *i=e[x];i;i=i->next)

         if(!b[f][i->n]){

             b[f][i->n]=;

             dfs(i->n,f);

         }

 }

 bool judge(){

     For(i,,n)

         For(j,i+,n)

             if(!b[i][j]&&!b[j][i])

                 return ;

     return ;

 }

 void clear(){

     memset(b,,sizeof(b));

     For(i,,)

         e[i]=;

 }

 int main(){

     in(T);

     while(T--){

         clear();

         in(n);in(m);

         For(i,,m){

             in(x);in(y);

             push(x,y);

         }

         For(i,,n)

             dfs(i,i);

         printf("Case %d: ",++cnt);

         if(judge())

             printf("Kalimdor is just ahead\n");

         else

             printf("The Burning Shadow consume us all\n");

     }

     return ;

 }