首页 > 代码库 > 二分图染色,DFS

二分图染色,DFS

题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1106

乍一眼看上去,好像二分图匹配,哎,想不出和哪一种匹配类似,到网上查了一下,DFS染色一遍就可以啦。

两种颜色的很好写。直接没有访问的是1,然后扫邻接表,为2,DFS邻接表。

技术分享
#include <bits/stdc++.h>using namespace std;#define maxn 105vector<int> G[maxn];int color[maxn],vis[maxn];void dfs(int u){    vis[u] = 1;    for(int i=0;i<G[u].size();i++)    {        int v = G[u][i];        if(!vis[v])        {            color[v] = 3 - color[u];            dfs(v);        }    }}int main(){    int n,t;    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        while(scanf("%d",&t),t)            G[i].push_back(t);    }    memset(vis,0,sizeof(vis));    memset(color,0,sizeof(color));    for(int i=1;i<=n;i++)    {        if(vis[i]==false)        {            color[i] = 1;            dfs(i);        }    }    int sum = 0;    for(int i=1;i<=n;i++)        if(color[i]==1)            sum++;    printf("%d\n",sum);    for(int i=1;i<=n;i++)        if(color[i]==1)            printf("%d ",i);    return 0;}
View Code

 

二分图染色,DFS