题目大意

题目链接

n个点（n <= 1e5）, m条有向边（m <= 2e5）, 最多之能删掉(m / 2)条边， 让其不成环，输出删除的边数和其索引号i（1 <= i <= m）

分析

只保留一个方向的边就行了。

我们可以认为边有两个方向， 一个是小索引号到大索引号， 另一个是大索引号到小索引号。

我们删除这两个方向中边数较少的那个方向的边， 即可， 最多删除的边数是（m / 2）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>

#define eps 1e-8
using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const ll ll_max = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> s;
    vector<int> l;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        if (u < v)
            s.push_back(i + 1);
        else
            l.push_back(i + 1);
    }
    auto ans = s.size() < l.size() ? s : l;
    cout << ans.size() << "\n";
    for (auto c : ans)
        cout << c << "\n";
    return 0;
}
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。