BAPC 2019 E.Exits in Excess（思维）

You own a disco called the Boogie Always Persists Club.The club is famous for its multiple interconnected rooms to twist and shout in. The rooms and the corridors between them form a maze-like structure and for added bonus you have made all the corridors one-way. However, it turns out not everyone is as happy with your club as you are. Recently the fire safety inspectors came by and they were not amused by what they saw: if a fire were to break out in one of the rooms, people would have great difficulty finding the fire exits and might even start running around in circles! They find this completely unacceptable and order you to improve things as quickly as possible. They insist that you have to make sure that no one can run around in circles in the club by removing some of the corridors between the rooms.

You, on the other hand, want to retain the attractiveness of the rooms. You do not want to remove too many corridors, because then people will no longer visit your club. You decide that at most half of the corridors may be removed.

Given the layout of the club, remove at most half of the corridors so that no cycles remain.

INPUT:

• One line containing the number of rooms 1 ≤ n ≤ 10^5 and the number of corridors 0 ≤ m ≤ 2 · 10^5.

 • Then follow m lines, each containing two different 1-based integers u and v indicating a corridor from room u to room v. There will be no corridor from a room to itself, nor will there be more than one corridor from one room to any other single room.

OUTPUT:

• On the first line, print a single integer 0 ≤ r ≤ m/2, the number of corridors to be removed. 

• Then print r lines containing the 1-based indices of the corridors that need to be removed to ensure that dancers cannot go around in circles in the disco anymore.

 If there are multiple valid solutions, you may output any one of them.

本题答案不唯一，符合要求的答案均正确

样例输入1复制

2 2
1 2
2 1

样例输出1复制

1
2

样例输入2复制

3 3
1 2
2 3
3 1

样例输出2复制

1
1

样例输入3复制

4 5
1 2
1 3
3 2
2 4
3 4

样例输出3复制

0

这场打的好惨啊qwq...当时没有仔细想这个题......

计蒜客现在才有了题库链接，今天来补题惹...

题意：

n个点，m条有向边，删除最多一半的边使得图中没有自环

思路：

比较 u < v 的边数和 u > v 的边数，把边数少的一部分都删掉

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 +7;
const int N = 2e5 + 10;

struct node
{
    int u, v;
}s[N];

int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        int a = 0, b = 0;
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d%d", &s[i].u, &s[i].v);
            if(s[i].u < s[i].v)
                a++;
            else
                b++;
        }
        bool flag = 0;
        if(a > b)
            flag = 1;
        cout<<min(a, b)<<'\n';
        for(int i = 1; i <= m; ++i)
        {
            if(flag)
            {
                if(s[i].u > s[i].v)
                    cout<<i<<'\n';
            }
            else
            {
                if(s[i].u < s[i].v)
                    cout<<i<<'\n';
            }
        }
    }
    return 0;
}