圖論練習題 摔跤 rassle 題解

【問題描述】

有兩種類型的職業摔跤手：一種是“好選手”，另一種是“差選手”。對於任何一對職業摔跤手來說，他們中可能有、也可能沒有比賽。假定有 n 位職業摔跤手，並且有一份清單，上面列出了 r 對參加比賽的摔跤手。寫一個程序,它能夠確定是否可能指定某些摔跤手為好選手，而將餘下的摔跤手指定為壞選手，從而使得每一場比賽都是在一個好選手與一個差選手之間進行。如果有可能做出這樣的指定，你的程序就應該將它產生出來，否則輸出無解“No”。

【輸入格式】

第1行有三個整數n，r。n是職業摔跤手的數量，r是比賽場數，它們之間用一個空格隔開。

接下來的r行，每行用兩個數V1，V2表示V1號摔跤手與V2號摔跤手比賽，選手從1開始編號。

【輸出格式】

輸出有兩行，第一行“好選手”的編號，第二行為“差選手”的編號，編號之間用一個空格隔開。

注意：為了鼓勵選手，使輸出答案唯一，請儘量多的將選手設為“好選手”，並且在可行條件下選擇編號小的選手為“好選手”。

如果無解，則輸出一行“No”。

 

【輸入輸出樣例】

rassle.in

4 4

1 2

1 4

2 3

3 4

rassle.out

1 3

2 4

【資料範圍】

n<=10000, r<=10000

【分析】

連通分量，判環。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25682

001 #include <cstdio>
002 #include <cstdlib>
003 #include <vector>
004 #include <algorithm>
005 #include <queue>
006 using namespace std;
007 const int MAXN=10001;
008 typedef vector<int> Vec;
009 Vec Suki;
010 Vec Kowa;
011 Vec Map[MAXN];
012 int Visited[MAXN];
013 int Dist[MAXN];
014 int Num[MAXN];
015
016 Vec temp,tmp1,tmp2;
017
018 int N,M;
019
020 void init()
021 {
022     scanf("%d %d\n",&N,&M);
023     int a,b;
024     for(int i=1;i<=M;i++)
025     {
026         scanf("%d %d\n",&a,&b);
027         Map[a].push_back(b);
028         Map[b].push_back(a);
029     }
030 }
031
032 int abs(int a)
033 {
034     return a>0?a:-a;
035 }
036
037 queue<int>Q;
038 bool bfs(int s)
039 {
040     Num[s]=1;
041     Dist[s]=0;
042     Visited[s]=true;
043    
044     Q.push(s);
045     int tmp,nxt;
046    
047     temp.clear();
048     tmp1.clear();
049     tmp2.clear();
050    
051     while(!Q.empty())
052     {
053         tmp=Q.front();
054         Q.pop();
055        
056         temp.push_back(tmp);
057        
058         for(unsigned int i=0;i<Map[tmp].size();i++)
059         {
060             nxt=Map[tmp][i];
061             if(Visited[nxt]==1)
062             {
063                 if(abs(Dist[tmp]-Dist[nxt])%2==0)
064                 {
065                     return false;
066                 }
067                 continue;
068             }
069             if(Visited[nxt]==0)
070             {
071                 Num[nxt]=!Num[tmp];
072                 Visited[nxt]=1;
073                 Dist[nxt]=Dist[tmp]+1;
074                 Q.push(nxt);
075             }
076         }
077     }
078     Vec::iterator iter;
079     int x;
080     for(iter=temp.begin();iter!=temp.end();iter++)
081     {
082         x=*iter;
083         if(Num[x]==1)
084             tmp1.push_back(x);
085         if(Num[x]==0)
086             tmp2.push_back(x);
087     }
088     if(tmp1.size()>=tmp2.size())
089     {
090         for(iter=tmp1.begin();iter!=tmp1.end();iter++)
091         {
092             x=*iter;
093             Suki.push_back(x);
094         }
095         for(iter=tmp2.begin();iter!=tmp2.end();iter++)
096         {
097             x=*iter;
098             Kowa.push_back(x);
099         }
100     }
101     else
102     {
103         for(iter=tmp1.begin();iter!=tmp1.end();iter++)
104         {
105             x=*iter;
106             Kowa.push_back(x);
107         }
108         for(iter=tmp2.begin();iter!=tmp2.end();iter++)
109         {
110             x=*iter;
111             Suki.push_back(x);
112         }
113     }
114     return true;
115 }
116
117 void solve()
118 {
119     bool flag;
120     init();
121    
122     for(int i=1;i<=N;i++)
123         Visited[i]=0,Num[i]=0,Dist[i]=10000000;
124    
125     for(int i=1;i<=N;i++)
126     {
127         if(Visited[i])
128             continue;
129         flag=bfs(i);
130         if(!flag)
131         {
132             printf("No\n");
133             return;
134         }
135     }
136    
137     Vec *Big;
138     Vec *Small;
139     if((Suki.size())>=Kowa.size()) {Big=&Suki,Small=&Kowa;}
140     if((Suki.size())<Kowa.size()) {Big=&Kowa,Small=&Suki;}
141    
142     sort(Suki.begin(),Suki.end());
143     sort(Kowa.begin(),Kowa.end());
144    
145     for(Vec::iterator iter=Big->begin();iter!=Big->end();iter++)
146         printf("%d ",*iter);
147     printf("\n");
148     for(Vec::iterator iter=Small->begin();iter!=Small->end();iter++)
149         printf("%d ",*iter);
150 }
151
152 int main()
153 {
154     freopen("rassle.in","r",stdin);
155     freopen("rassle.out","w",stdout);
156     solve();
157     return 0;
158 }