10912022-03-01 00:36:32peti1234Hálózatjavításcpp14Accepted 50/5037ms8028 KiB
#include <bits/stdc++.h>

using namespace std;
const int c=10005;
int n, m, ki[c], id[c], h, kezd, maxi, k[c];
vector<int> sz[c], sz2[c], kor;
bool v[c], v2[c], rossz[c];


void dfs(int a) {
    v[a]=true;
    for (auto x:sz[a]) {
        if (rossz[x]) continue;
        if (!v[x]) {
            dfs(x);
        } else kor.push_back(x);
        kor.push_back(a);
        return;
    }
}
int t(int a, int b) {
    return (a<=b ? b-a : n+b-a);
}
int p(int a) {
    return (a<h ? a+1 : 1);
}
void dfs2(int a) {
    if (id[a] && t(kezd, id[a])>t(kezd, maxi)) {
        maxi=id[a];
    }
    if (v2[a]) {
        return;
    }
    v2[a]=true;
    for (auto x:sz[a]) {
        if (id[a] && id[x] && p(id[a])==id[x]) {
            continue;
        }
        dfs2(x);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        int a, b;
        cin >> a >> b;
        sz[a].push_back(b);
        sz2[b].push_back(a);
    }
    queue<int> q;
    for (int i=1; i<=n; i++) {
        ki[i]=sz[i].size();
        if (!ki[i]) {
            q.push(i);
        }
    }
    while (q.size()>0) {
        int a=q.front();
        rossz[a]=1;
        q.pop();
        for (auto x:sz2[a]) {
            ki[x]--;
            if (!ki[x]) {
                q.push(x);
            }
        }
    }
    for (int i=1; i<=n; i++) {
        if (!rossz[i]) {
            dfs(i);
            break;
        }
    }
    while (kor.back()!=kor[0]) {
        kor.pop_back();
    }
    reverse(kor.begin(), kor.end());
    h=kor.size();
    h--;
    for (int i=1; i<=h; i++) {
        id[kor[i]]=i;
    }

    /*for (int i=1; i<=h; i++) {
        cout << kor[i] << " ";
    }
    cout << "\n";*/

    for (int i=1; i<=h; i++) {
        kezd=i, maxi=i;
        dfs2(kor[i]);
        int s=kezd;
        //cout << "fontos " << kezd << " " << maxi << "\n";
        while (s!=maxi) {
            k[s]=1;
            s=p(s);
        }
    }


    int db=0;
    for (int i=1; i<=h; i++) {
        if (!k[i]) {
            db++;
        }
    }
    cout << db << "\n";
    for (int i=1; i<=h; i++) {
        if (!k[i]) {
            cout << kor[i] << " " << kor[p(i)] << "\n";
        }
    }
    // minden csucsbol dfs, valami jo adatszerkezet, a felesleges elekre
    // O(n^2) is jo
    return 0;
}
/*
8 11
5 7
7 1
1 2
2 3
3 4
2 6
6 5
4 5
5 8
7 8
1 8
*/
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/02ms2792 KiB
2Accepted0/08ms5472 KiB
3Accepted1/12ms3036 KiB
4Accepted1/12ms3044 KiB
5Accepted1/12ms3048 KiB
6Accepted1/12ms3312 KiB
7Accepted1/12ms3332 KiB
8Accepted2/23ms3612 KiB
9Accepted2/23ms3708 KiB
10Accepted2/22ms3396 KiB
11Accepted2/24ms3976 KiB
12Accepted2/23ms3496 KiB
13Accepted2/28ms4728 KiB
14Accepted2/24ms4396 KiB
15Accepted2/212ms5148 KiB
16Accepted2/26ms4996 KiB
17Accepted2/214ms5668 KiB
18Accepted2/28ms6436 KiB
19Accepted2/28ms6256 KiB
20Accepted2/223ms6748 KiB
21Accepted2/28ms6932 KiB
22Accepted2/221ms7084 KiB
23Accepted3/38ms7272 KiB
24Accepted4/48ms7448 KiB
25Accepted4/48ms7620 KiB
26Accepted4/437ms8028 KiB