Cod sursa(job #2086387)

Utilizator amaliarebAmalia Rebegea amaliareb Data 11 decembrie 2017 23:26:26
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int MaxN = 100005;
int n, m, seen[MaxN], onst[MaxN], low[MaxN], nrc, ind;
vector<int> gr[MaxN], comp[MaxN];
stack<int> st;

void dfs(int node)
{
    seen[node] = ++ind;
    st.push(node);
    onst[node] = 1;
    low[node] = seen[node];
    for (auto son: gr[node])
        if (!seen[son])
        {
            dfs(son);
            low[node] = min(low[node], low[son]);
        }
        else if (onst[son]) low[node] = min(low[node], seen[son]);
    if (low[node] == seen[node])
    {
        ++nrc;
        while (st.top() != node)
        {
            comp[nrc].push_back(st.top());
            onst[st.top()] = 0;
            st.pop();
        }
        comp[nrc].push_back(st.top());
        onst[st.top()] = 0;
        st.pop();
    }
}

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        f >> x >> y;
        gr[x].push_back(y);
    }
    for (int i = 1; i <= n; i++) if (!seen[i]) dfs(i);
    g << nrc << '\n';
    for (int i = 1; i <= nrc; i++)
    {
        for (auto x: comp[i]) g << x << ' ';
        g << '\n';
    }
    return 0;
}