首页 > 代码库 > hihocoder-1121-二分图一?二分图判定

hihocoder-1121-二分图一?二分图判定

2024-08-12 20:53:16   220人阅读

题目背景：男女相亲图，n个点m条边，数据范围n<=10000，m<=40000，判断输入的数据是否满足任意一条边的两个端点分别为男和女

分析：简单二分图，选择一个端点开始染色，我的做法是vis[i]=-1然后从i点出发的边的另一个端点都染成vis[j]=1，初始化memset(vis,0,sizeof(vis))表示所有端点还没有被染色

深搜，或者说递归，从一个端点开始染色：

1.如果与他相连的另一个端点还没染色就染成与他相反的颜色，且递归这个端点

2.如果与他相连的另一个端点已经染色，且和他相同直接返回false

注意：递归不能直接vis[1]=-1;return dfs(1)；因为这个图可能不是连通的，所以要用一个for循环来寻找还没被染色的端点，然后开始递归

 1 #include<iostream> 2 #include<vector> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 using namespace std; 7  8 int t,n,m; 9 vector<vector<int> > v;10 int vis[10005];11 12 bool dfs(int x)13 {14     for(int i=0;i<v[x].size();i++){15         int y=v[x][i];16         if(!vis[y]){17             vis[y]=-vis[x];18             if(!dfs(y)) return false;19         }20         else if(vis[y]==vis[x]) return false;21     }22     return true;23 }24 25 int main()26 {27     cin>>t;28     while(t--){29         cin>>n>>m;30         v.clear();31         v.resize(n+1);32         memset(vis,0,sizeof(vis));33         while(m--){34             int x,y;35             cin>>x>>y;36             v[x].push_back(y);37             v[y].push_back(x);38         }39         int ok=1;40         for(int i=1;i<=n;i++){41             if(!vis[i]){42                 vis[i]=-1;43                 if(!dfs(i)){44                     ok=0;45                     break;46                 }47             }48         }49         if(ok) cout<<"Correct"<<endl;50         else cout<<"Wrong"<<endl;51     }52 }

 

hihocoder-1121-二分图一?二分图判定


联系
我们