hdu - 1829 - A Bugs Life

題意：判斷一個圖是否為二分圖。
 

——>>直接dfs。

[cpp]  #include<cstdio>  
#include<cstring>  
#include<vector>  
 
using namespace std; 
 
const int maxn = 2000 + 10; 
int color[maxn], n, m; 
bool vis[maxn]; 
vector<int> G[maxn]; 
 
bool dfs(int u)     //判斷u的在的連通分支是否為二分圖  
{ 
    vis[u] = 1; 
    int i, len = G[u].size(); 
    for(i = 0; i < len; i++) 
    { 
        int v = G[u][i]; 
        if(color[u] == color[v]) return false; 
        if(!color[v]) 
        { 
            color[v]= 3 - color[u]; 
            if(!dfs(v)) return false; 
        } 
    } 
    return true; 
} 
 
int main() 
{ 
    int cnt = 1, T, i, x, y; 
    scanf("%d", &T); 
    while(T--) 
    { 
        scanf("%d%d", &n, &m); 
        for(i = 0; i <= n; i++) G[i].clear(); 
        for(i = 1; i <= m; i++) 
        { 
            scanf("%d%d", &x, &y); 
            G[x].push_back(y); 
            G[y].push_back(x); 
        } 
        memset(color, 0, sizeof(color)); 
        memset(vis, 0, sizeof(vis)); 
        printf("Scenario #%d:\n", cnt++); 
        bool ok = 1; 
        for(i = 1; i <= n; i++) 
        { 
            if(!vis[i]) 
            { 
                color[i] = 1; 
                if(!dfs(i)) 
                { 
                    ok = 0; 
                    break; 
                } 
            } 
        } 
        if(ok) printf("No suspicious bugs found!\n\n"); 
        else printf("Suspicious bugs found!\n\n"); 
    } 
    return 0; 
} 

#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

const int maxn = 2000 + 10;
int color[maxn], n, m;
bool vis[maxn];
vector<int> G[maxn];

bool dfs(int u)     //判斷u的在的連通分支是否為二分圖
{
    vis[u] = 1;
    int i, len = G[u].size();
    for(i = 0; i < len; i++)
    {
        int v = G[u][i];
        if(color[u] == color[v]) return false;
        if(!color[v])
        {
            color[v]= 3 - color[u];
            if(!dfs(v)) return false;
        }
    }
    return true;
}

int main()
{
    int cnt = 1, T, i, x, y;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        for(i = 0; i <= n; i++) G[i].clear();
        for(i = 1; i <= m; i++)
        {
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        memset(color, 0, sizeof(color));
        memset(vis, 0, sizeof(vis));
        printf("Scenario #%d:\n", cnt++);
        bool ok = 1;
        for(i = 1; i <= n; i++)
        {
            if(!vis[i])
            {
                color[i] = 1;
                if(!dfs(i))
                {
                    ok = 0;
                    break;
                }
            }
        }
        if(ok) printf("No suspicious bugs found!\n\n");
        else printf("Suspicious bugs found!\n\n");
    }
    return 0;
}