首页 > 代码库 > UVA 1572 Self-Assembly

UVA 1572 Self-Assembly

2024-07-13 09:34:57   219人阅读

拓扑排序，以边上标号为点，正方形为边，拓扑图中存在有向环时unbounded，否则bounded；

注意：仔细处理输入；

　　   遍历一个点时，下一次遍历拼上的下一个方形边；即假设遍历到 A+ 时，下次从 A- 开始遍历；

 

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6     int n; 7     int g[60][60]; 8     int visit[60]; 9 10 int dfs (int u){11     visit[u]=-1;12     if (u%2)13         u--;14     else u++;15     for (int i=0;i<52;i++)16         if (g[u][i]){17             if (visit[i]<0)18                 return false ;19             else if (!visit[i]&&!dfs (i))20                 return false ;21         }22     if (u%2) u--;else u++;23     visit[u]=1;24     return true ;25 }26 27 int topo (){28     for (int u=0;u<52;u++)29         if (!visit[u]&&!dfs (u))30             return false ;31     return true ;32 }33 34 int main (){35     while (~scanf ("%d",&n)){36         memset (visit,0,sizeof visit);37         memset (g,0,sizeof g);38         for (int i=0;i<n;i++){39             char s[10];40             scanf ("%s",s);41             for (int j=0;j<4;j++){42                 if (s[j*2]==‘0‘)43                     continue ;44                 int tempj=(s[j*2]-‘A‘)*2;45                 //g[tempj][tempj+1]=g[tempj+1][tempj]=1;46                 tempj+=s[j*2+1]==‘+‘?0:1;47                 for (int o=j+1;o<4;o++){48                     if (s[o*2]==‘0‘)49                         continue ;50                     int tempo=(s[o*2]-‘A‘)*2;51                     tempo+=s[o*2+1]==‘+‘?0:1;52                     g[tempj][tempo]=g[tempo][tempj]=1;53                 }54             }55         }56         //for (int i=0;i<52;i++){for (int j=0;j<52;j++){cout<<g[i][j];}cout<<endl;}57         if (topo ())58             printf ("bounded\n");59         else printf ("unbounded\n");60     }61     return 0;62 }


联系
我们