Codeforces 623A Graph and String (构造)

题目链接：http://codeforces.com/problemset/problem/623/A

题意：一个仅包含abc这3个字母的字符串，a与b和自身相连，b与ac和自身相连，c与b与自身相连，给出字符串每一位的相连情况，要求构造出这样一个字符串

思路：b与ac和自己都相连，所以连有n-1个点的位置必定是b，其他的点我们找一点和与该点相连的点设为a，其他设为c，最后n^2判断是否符合题意就可以

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

int d[530],vis[530],Link[530][530];
vector <int> G[530];
char ans[530];

void dfs(int u)
{
    if (ans[u]=='b')
        return;
        ans[u]='a';
    for (int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if (!vis[v])
        {
            vis[v]=1;
            dfs(G[u][i]);
        }
    }
}


int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        memset(G,0,sizeof(G));
        memset(d,0,sizeof(d));
        memset(ans,0,sizeof(ans));
        memset(vis,0,sizeof(vis));
        memset(Link,0,sizeof(Link));
        for (int i=0;i<m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            Link[a][b]=1;
            Link[b][a]=1;
            G[a].push_back(b);
            G[b].push_back(a);
            d[a]++;
            d[b]++;
        }

        for (int i=1;i<=n;i++)
        {
            if (d[i]==n-1)
                ans[i]='b';
        }

        for (int i=1;i<=n;i++)
        {
            if (ans[i]!='b')
            {
                dfs(i);
                break;
            }
        }

        for (int i=1;i<=n;i++)
        {
            if (ans[i]!='a' && ans[i]!='b')
            {
                ans[i]='c';
            }
        }

        int flag=1;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                if (i==j) continue;
                if (ans[i]==ans[j])
                {
                    if (!Link[i][j])
                        flag=0;
                }
            }
        }

        if (flag) printf("Yes\n%s\n",ans+1);
        else printf("No\n");

    }
}