Cod sursa(job #2702387)

Utilizator beingsebiPopa Sebastian beingsebi Data 3 februarie 2021 20:32:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
vector<vector<int>> v, tv, rez;
stack<int> st;
vector<bool> bif;
void dfs1(int);
void dfs2(int);
int main()
{
    f >> n >> m;
    bif.resize(n + 1);
    v.resize(n + 1);
    tv.resize(n + 1);
    for (int x, y; m; m--)
        f >> x >> y, v[x].emplace_back(y), tv[y].emplace_back(x);
    for (int i = 1; i <= n; i++)
        if (!bif[i])
            dfs1(i);
    while (!st.empty())
    {
        int ac = st.top();
        st.pop();
        if (bif[ac])
            rez.emplace_back(vector<int>()), dfs2(ac);
    }
    g << rez.size() << '\n';
    for (const auto &i : rez)
    {
        for (const auto &j : i)
            g << j << " ";
        g << '\n';
    }
    return 0;
}
void dfs1(int x)
{
    bif[x] = 1;
    for (const auto &i : v[x])
        if (!bif[i])
            dfs1(i);
    st.push(x);
}
void dfs2(int x)
{
    bif[x] = 0;
    rez.back().emplace_back(x);
    for (const auto &i : tv[x])
        if (bif[i])
            dfs2(i);
}