D - 欧拉路

题意：判断一个无向图是否是欧拉回路
题解：
无向图存在欧拉回路的充要条件：
一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数,且该图是连通图
所以先用并查集判断图的连通性，在统计各点的度。

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1e3 + 500;
int fa[maxn], r[maxn];
int  n, m, s, t, cnt[maxn];
void init() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        r[i] = 1;  
    }
}
int Find(int x) {
    while (x != fa[x]) {
        x = fa[x]; 
    }
    return x;
}
void Union(int x, int y) {
    int fx = Find(x), fy = Find(y);
    if (fx == fy) return;
    if (r[fx] < r[fy]) {
        fa[fx] = fy; 
    }
    else {
        fa[fy] = fx;
        if (r[fx] == r[fy]) r[fx]++; 
    }
}
int main()
{
    while (cin >> n) {
        if (n == 0)
            break;
        cin >> m;
        init();
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < m; i++)
        {
            cin >> s >> t;
            Union(s, t);
            cnt[s]++;
            cnt[t] ++;
        }
        int k = 0;
        for (int i = 1; i <= n; i++)
        {
            if (Find(i) != Find(1))
                k = 1;
            if (cnt[i] % 2 != 0)
                k = 1;
        }
        if (k)
            cout << 0 << endl;
        else
            cout << 1 << endl;
    }
}

E - 拓扑排序

题意：对一个有向图进行拓扑排序
题解：
循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
比较坑的是题目中可能会存在同一条边重复输入的问题。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 550;
bool e[maxn][maxn];
int in[maxn],n,m,s,t;
priority_queue<int, vector<int>, greater<int> > q;
void ans()
{
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 0)
            q.push(i);
    }
    int cnt = 1;
    while (!q.empty())
    {
        int s = q.top();
        q.pop();
        if (cnt != n)
        {
            cout << s << " ";
            cnt++;
        }
        else
            cout << s << endl;
        for (int i = 1; i <= n; i++)
        {
            if (!e[s][i])
                continue;
            in[i]--;
            if (!in[i])
                q.push(i);
        }
    }
}
int main()
{
    while (cin >> n >> m)
    {
        memset(e, 0, sizeof(e));
        memset(in, 0, sizeof(in));
        while (m--)
        {
            cin >> s >> t;
            if (e[s][t] == 0) {
                e[s][t] = 1;
                in[t]++;
            }
        }
        ans();
    }
}

F - 拓扑排序

题意：年终要给 n 个员工发奖金，每个人的起始金额是888，有些人觉得自己做的比另一个人好所以应该多得一些钱，问最少需要花多少钱，如果不能满足所有员工的要求，输出 -1。
题解：进行拓扑排序，依照入度情况对888进行加法操作。

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 10050;
vector<int>e[maxn];
int ans[maxn];  
int in[maxn];  
queue<int> q;
int n, m;
void solve()
{
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 0)   
        {
            q.push(i);
            ans[i] = 888;
            in[i]--;
        }
    }
    while (!q.empty())
    {
        int s = q.front();
        q.pop();
        for (int i = 0; i < e[s].size(); i++)
        {
            in[e[s][i]]--;
            if (in[e[s][i]] == 0)
            {
                q.push(e[s][i]);
                ans[e[s][i]] = ans[s] + 1;
                in[e[s][i]]--;
            }
        }
    }
    int flag = 0;
    int cnt = 0;  
    for (int i = 1; i <= n; i++)
    {
        if (in[i] != -1)
            flag++;  //说明存在回路，无法确定
    }
    if (flag != 0)
        cout << -1 << endl;
    else
    {
        for (int i = 1; i <= n; i++)
            cnt += ans[i];
        cout << cnt << endl;
    }
}
int main()
{
    while (cin>>n>>m)
    {
        for (int i = 0; i <= n; i++)
            e[i].clear();
        while (!q.empty())
            q.pop();
        memset(in, 0, sizeof(in));
        memset(ans, 0, sizeof(ans));
        for (int i = 0; i < m; i++)
        {
            int s, t;
            cin >> t >> s;
            in[t]++;
            e[s].push_back(t);
        }
        solve();
    }
}