POJ 3660 Cow Contest

Description

n头牛参加比赛，给你m对关系（譬如给你a和b，那么给的就是a必赢b，当然，b能赢c，那么a也能赢c），问能确定多少头牛的排名。

传送门

Floyd 传递闭包

传递闭包的含义指通过传递性推导出尽量多的元素之间的关系

用flod算法将所有的关系进行传递，只要u能胜v，那么我们就将d[u][v]设为1，最后如果两者之间有d[u][v]=0且d[v][u]=0则u、v两点不知排名

Code

#include <set>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n, m;
bool beat[105][105];

///一个可怕的地方：我所有的循环都写了++i
void floyd()
{
    for(int k = 1; k <= n; ++k)///++i写太习惯了
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(beat[i][k] && beat[k][j])
                    beat[i][j] = 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    int a, b;
    memset(beat, 0, sizeof(beat));
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d", &a, &b);
        beat[a][b] = 1;
    }
    floyd();
    int ans = n;
    set<int> st;
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j)
            if(beat[i][j] == 0 && beat[j][i] == 0)
            {
                st.insert(i);
                st.insert(j);
            }
    cout << ans - st.size() << '\n';
    return 0;
}

Wrong answer(并查集+拓扑排序)

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

int n, m;///n个点，m个关系描述
int init_in[105], in[105], init_out[105];
vector<int> ans;
vector<int> v[105];

int pre[105];

void init()
{
    for(int i = 0; i <= n; ++i)
    {
        pre[i] = i;
        v[i].clear();
    }
}

int found(int x)
{
    if(x != pre[x])
        pre[x] = found(pre[x]);
    return pre[x];
}

void unite(int a, int b)
{
    int x = found(a);
    int y = found(b);
    if(x != y)
        pre[y] = x;
    return ;
}

void bfs()
{
    queue<int> q;
    for(int i = 1; i <= n; ++i)///从1~n
        if(!init_in[i])
            q.push(i);

    int init_qsz = q.size();
    while(q.size())
    {
        int first = q.front();
        ans.push_back(first);
        q.pop();

        for(int i = 0; i < v[first].size(); ++i)
        {
            in[ v[first][i] ]--;
            if(in[ v[first][i] ] == 0)
                q.push(v[first][i]);
        }
    }

    int res = 0;
    int sz = ans.size();
///原从0到顶遍历，后改为从顶到0，结果++i没换，编译器不报错一直RE
    ///应有四种类型：树形、倒树形、菱形、“嚣”字形
    if(init_qsz != 1)
        for(int i = sz - 1; i >= 0; --i)///树形
        {
            if(init_in[ ans[i] ] == 1)
                res++;
            else
                break;
        }
    else
        for(int i = 0; i < sz; ++i)///倒树形
        {
            if(init_out[ ans[i] ] == 1)
                res++;
            else
                break;
        }
    cout << res + 1 << '\n';
}

int main()
{
    scanf("%d%d", &n, &m);

    init();
    memset(init_in, 0, sizeof(init_in));
    memset(in, 0, sizeof(in));

    int a, b;
    map<int, map<int, bool> > mp;
    for(int i = 0; i < m; ++i)
    {
        scanf("%d%d", &a, &b);

        if(mp[a][b])///map嵌套除重
            continue;
        else
            mp[a][b] = 1;

        unite(a, b);
        v[a].push_back(b);
        init_out[a]++;
        init_in[b]++;
        in[b]++;
    }
    bool flag = 1;
    int standard = found(1);
    for(int i = 2; i <= n; ++i)
        if(found(i) != standard)
        {
            flag = 0;
            break;
        }
    if(!flag)
        cout << '0' << '\n';
    else
        bfs();
    return 0;
}