Cod sursa(job #2857443)

Utilizator norryna07Alexandru Norina norryna07 Data 25 februarie 2022 17:10:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
#define N 100005
using namespace std;

ifstream fin ("ctc.in");
ofstream fout ("ctc.out");

vector < vector <int> > g, cmp;
vector <int> low, dist;
bitset <N> viz, instack;
stack <int> st;
int n, m, nrc;
int timp;

void citire()
{
    fin>>n>>m;
    g = vector < vector <int> > (n+2);
    dist = low = vector <int> (n+2);
    int x, y;
    for (int i=1; i<=m; ++i)
    {
        fin>>x>>y;
        g[x].push_back(y);
    }
}

void dfs(int x)
{
    viz[x]=1;
    dist[x]=low[x]=++timp;
    st.push(x); instack[x]=1;
    for (auto y:g[x])
        if (viz[y])
        {
            if (instack[y]) low[x]=min(low[x], dist[y]);
        }
        else 
        {
            dfs(y);
            low[x]=min(low[x], low[y]);
        }
    if (low[x]==dist[x])
    {
        nrc++;
        cmp.push_back(vector <int> (0));
        while (st.top()!=x)
        {
            cmp[nrc-1].push_back(st.top());
            instack[st.top()]=0;
            st.pop();
        }
        cmp[nrc-1].push_back(st.top());
        instack[st.top()]=0;
        st.pop();
    }
}

void solve()
{
    for (int i=1; i<=n; ++i)
        if (!viz[i]) dfs(i);
    fout<<nrc<<'\n';
    for (int i=0; i<nrc; ++i)
    {
        for (auto y:cmp[i]) fout<<y<<' ';
        fout<<'\n';
    }
}

int main()
{
    citire();
    solve();
    return 0;
}