A - 拓扑排序

题意：有一些任务要完成，但是有部分任务不能直接去做，要先完成某些前置任务才可以 开始做。要求输入一个完成所有任务的合法顺序。

题解：直接按拓扑排序的方法来做，先输出入读为0的点，再把这个点从图中删去，同时与这个点相连的其他点的入度减小。重复这个过程直到所有点都输出。

#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n,m,in_du[110];
vector<int>G[110];
queue<int>Q;
void topsort()
{
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        printf("%d ",u);
        for(int i = 0;i < (int)G[u].size();i++)
        {
            int v = G[u][i];
            in_du[u]--,in_du[v]--;
            if(in_du[v] == 0)
            {
                Q.push(v);
            }
        }
    }
}
int main()
{
    while(scanf("%d %d",&n,&m) && (n || m))
    {
        for(int i = 0;i <= n;i++) G[i].clear();
        memset(in_du,0,sizeof(in_du));
        for(int i = 1;i <= m;i++)
        {
            int u,v;
            scanf("%d %d",&u,&v);
            G[u].push_back(v);
            in_du[v]++;
        }
        for(int i = 1;i <= n;i++)
        {
            if(in_du[i] == 0)
                Q.push(i);
        }
        topsort();
        printf("\n");
    }
    return 0;
}

B - 欧拉路

题意：给出一些单词，判断这些单词能不能首尾相接连在一起，当一个单词的尾字母和另一个单词的首字母相同时可以接在一起。

题解：把单词的首尾字母抽象成点，然后判断能不能形成欧拉图或者半欧拉图。有向图形成欧拉图的条件是每个点的出度都等于入读，形成半欧拉图的条件是起点的出度减入读等于一，终点的入读减出度等于一，其他点的出度和入读相同。同时还需要是一个连通图。不满足以上条件的都不成立。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int fa[26],vis[26],in[26],out[26],n;
int Find(int x)
{
    if(x == fa[x]) return x;
    else return fa[x] = Find(fa[x]);
}
void Union(int x,int y)
{
    int fx = Find(x),fy = Find(y);
    if(fx != fy)    fa[fx] = fy;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        memset(out,0,sizeof(out));
        memset(in,0,sizeof(in));
        for(int i = 0;i < 26;i++) fa[i] = i;
        scanf("%d",&n);
        string s;
        for(int i = 1;i <= n;i++)
        {
            cin>>s;
            char fi = s[0];
            char se = s[s.size() - 1];
            vis[fi - 'a'] = 1,vis[se - 'a'] = 1;
            out[fi - 'a']++,in[se - 'a']++;
            Union(fi - 'a',se - 'a');
        }
        int flag = 1,root = 0;
        for(int i = 0;i < 26;i++)
        {
            if(vis[i] == 1 && Find(i) == i)
                root++;
        }
        if(root > 1)
        {
            printf("The door cannot be opened.\n");
            continue;
        }
        int st = 0,ed = 0;
        for(int i = 0;i < 26;i++)
        {
            if(vis[i] == 1 && out[i] != in[i])
            {
                if(in[i] - out[i] == 1) ed++;
                else if(in[i] - out[i] == -1) st++;
                else flag = 0;
            }
        }
        if(!((st == 1 && ed == 1) || (st == 0 && ed == 0))) flag = 0;
        if(flag == 0) printf("The door cannot be opened.\n");
        else          printf("Ordering is possible.\n");
    }
    return 0;
}

C - 欧拉路

题意：一个房子里有编号为0到n-1的n个房间，有一些房间的门是开着的，给出起点房间及每个开着门的房间与其他开着门的房间相连的情况，问能不能经过所有门一次最后回到0号房间。如果能输出经过的门的数量。

题解：这道题的正确做法应该是需要判是否连通的，但是我判了连通后wa了，然后不判连通就ac了，去网上找判连通a了的代码也没找到。那如果在已知连通的情况下判断就是要么从0出发再回到0，那么是判欧拉图。或者从其他点出发再回到0，那么就是判半欧拉图。无向图判断欧拉图的条件是每个点的度数为偶数。半欧拉图的条件是起点和终点的度数为奇数，其他点的度数为偶数。

//AC代码，但是没有判连通//
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int st,n,du[110];
char str[110];
int main()
{
    string s;
    while(cin>>s)
    {
        int num = 0;
        if(s == "ENDOFINPUT") break;
        if(s == "END") continue;
        if(s == "START") scanf("%d %d",&st,&n);
        memset(du,0,sizeof(du));
        getchar();
        for(int i = 0;i < n;i++)
        {
            gets(str);
            int cont = 0;
            for(int j = 0;j <= (int)strlen(str);j++)
            {
                if(str[j] >= '0' && str[j] <= '9') cont = cont * 10 + str[j] - '0';
                else
                {
                    if(cont > 0)
                    {
                        du[i]++;
                        du[cont]++;
                        num++;
                        cont = 0;
                    }
                }
            }
        }
        int flag = 1;
        if(st == 0)
        {
            for(int i = 0;i < n;i++)
            {
                if(du[i] % 2 == 1) flag = 0;
            }
            if(flag == 0) printf("NO\n");
            else          printf("YES %d\n",num);
        }
        else
        {
            int cont = 0;
            for(int i = 0;i < n;i++)
            {
                if(i == 0 && du[i] % 2 != 1) flag = 0;
                if(i > 0 && du[i] % 2 == 1) cont++;
            }
            if(cont != 1) flag = 0;
            if(flag == 0) printf("NO\n");
            else          printf("YES %d\n",num);
        }
    }
    return 0;
}