Cod sursa(job #2856790)

Utilizator ElizaTElla Rose ElizaT Data 24 februarie 2022 12:05:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;
vector <int> e[NMAX + 5],inv[NMAX + 5];
int viz[NMAX + 5],ans[2 * NMAX + 5],viz1[NMAX + 5];
stack <int> st;
int cnt = 0;

void dfs1(int node) {
    viz1[node] = 1;
    for (int i = 0;i < inv[node].size();i++)
        if (!viz1[inv[node][i]])
            dfs1(inv[node][i]);
    ans[cnt++] = node;
}
void dfs(int node) {
    viz[node] = 1;
    for (int i = 0;i < e[node].size();i++)
        if (!viz[e[node][i]])
            dfs(e[node][i]);
    st.push(node);
}
int main()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    int n,m,a,b,anss = 0;
    fin >> n >> m;
    for (int i = 0;i < m;i++) {
        fin >> a >> b;
        e[a].push_back(b);
        inv[b].push_back(a);
    }
    for (int i = 1;i <= n;i++)
        if (!viz[i])
            dfs(i);
    while (!st.empty()) {
        a = st.top();
        st.pop();
        if (!viz1[a]) {
            dfs1(a);
            ans[cnt++] = -1;
            anss++;
        }
    }
    fout << anss << '\n';
    for (int i = 0;i < cnt;i++) {
        if (ans[i] == -1)
            fout << '\n';
        else
            fout << ans[i] << " ";
    }
    return 0;
}