Cod sursa(job #3003341)

Utilizator zoabaZob Alexandru Mihai zoaba Data 15 martie 2023 17:54:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 100005;
vector<int>G[NMAX],T[NMAX],ans[NMAX];
int viz[NMAX],c[NMAX],cc;
int n,m;
stack<int> st;

void dfs(int nod)
{
    viz[nod] = 1;
    for(auto x : G[nod])
        if(!viz[x])
            dfs(x);
    st.push(nod);
}

void dfst(int nod)
{
    c[nod] = cc;
    ans[cc].push_back(nod);
    for(auto x : T[nod])
        if(!c[x])
            dfst(x);
}

int main()
{
    int i,x,y;
    fin >> n >> m;
    for(i=1;i<=m;++i)
    {
        fin >> x >> y;
        G[x].push_back(y);
        T[y].push_back(x);
    }

    for(i=1;i<=n;++i)
        if(!viz[i])
            dfs(i);

    while(!st.empty())
    {
        if(!c[st.top()])
        {
            cc++;
            dfst(st.top());
        }
        st.pop();
    }

    fout << cc << '\n';
    for(i=1;i<=cc;++i)
    {
        for(auto x : ans[i])
            fout << x << ' ';
        fout << '\n';
    }
    return 0;
}