hihocoder 第三十三周二分图一•二分图判定

判断是否为二分图

算法：

选取一个未染色的点u进行染色
遍历u的相邻节点v：若v未染色，则染色成与u不同的颜色，并对v重复第2步；若v已经染色，如果 u和v颜色相同，判定不可行退出遍历。
若所有节点均已染色，则判定可行。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<string>
 6 #include<queue>
 7 #include<algorithm>
 8 #include<map>
 9 #include<iomanip>
10 #include<climits>
11 #include<string.h>
12 #include<cmath>
13 #include<stdlib.h>
14 #include<vector>
15 #include<stack>
16 using namespace std;
17 #define INF 1000000007
18 #define MAXN 40010
19 #define Mod 1000007
20 #define N 10007
21 #define NN 30
22 #define sigma_size 3
23 const int maxn = 6e5 + 10;
24 using namespace std;
25 typedef long long LL;
26 
27 bool vis[10010];
28 bool col[10010];
29 vector<int> G[10010];
30 int n, m;
31 int u, v;
32 
33 bool dfs(int u, bool c)
34 {
35     if (vis[u])
36         return col[u] == c;
37     else {
38         vis[u] = true;
39         col[u] = c;
40         for (int i = 0; i < G[u].size(); ++i) {
41             int v = G[u][i];
42             if (!dfs(v,!c)) return false;    
43         }
44         return true;
45     }
46 }
47 
48 void process()
49 {
50     memset(vis,0,sizeof(vis));
51     memset(col,0,sizeof(col));
52     for (int i = 0; i < n; ++i)
53         G[i].clear();
54     cin >> n >> m;
55     for (int i = 0; i < m; ++i) {
56         cin >> u >> v;
57         u--, v--;
58         G[u].push_back(v);
59         G[v].push_back(u);
60     }
61     bool re = 1;
62     for (int i = 0; i < n; ++i)
63         if (!vis[i])
64             re &= dfs(i, 0);
65     if (re)    puts("Correct");
66     else puts("Wrong");
67 }
68 
69 int main()
70 {
71     int T;
72     cin >> T;
73     while (T--)
74         process();
75     //system("pause");
76     return 0;
77 }

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<string>
 6 #include<queue>
 7 #include<algorithm>
 8 #include<map>
 9 #include<iomanip>
10 #include<climits>
11 #include<string.h>
12 #include<cmath>
13 #include<stdlib.h>
14 #include<vector>
15 #include<stack>
16 #include<set>
17 using namespace std;
18 #define INF 1000000007
19 #define MAXN 40010
20 #define Mod 1000007
21 #define N 10007
22 #define NN 30
23 #define sigma_size 3
24 const int maxn = 6e5 + 10;
25 using namespace std;
26 typedef long long LL;
27 
28 int n, m;
29 int u, v;
30 int color[10010];
31 vector<int> G[40010];
32 
33 bool bipartite(int u)
34 {
35     for (int i = 0; i < G[u].size(); ++i) {
36         int v = G[u][i];
37         if (color[v] == color[u]) return false;
38         if (!color[v]) {
39             color[v] = 3 - color[u];
40             if (!bipartite(v)) return false;
41         }
42     }
43     return true;
44 }
45 
46 void process()
47 {
48     cin >> n >> m;
49     memset(color, 0, sizeof(color));
50     for (int i = 0; i <= n; ++i)
51         G[i].clear();
52     for (int i = 0; i < m; ++i) {
53         cin >> u >> v;
54         G[u].push_back(v);
55         G[v].push_back(u);
56     }
57     bool re = true;
58     for (int i = 1; i <= n; ++i)
59         if (!color[i]) {
60             color[i] = 1;
61             re &= bipartite(i);
62         }
63     if (re) puts("Correct");
64     else puts("Wrong");
65 }
66 
67 int main()
68 {
69     int T;
70     cin >> T;
71     while (T--)
72         process();
73     //system("pause");
74     return 0;
75 }

hihocoder 第三十三周 二分图一•二分图判定

hihocoder 第三十三周二分图一•二分图判定