Cod sursa(job #2375725)

Utilizator mirelPmirel p mirelP Data 8 martie 2019 11:47:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMAX=100005;
stack<int>st,st2;
vector<int>G[NMAX],T[NMAX],sol[NMAX];
int n,i,j,k,l,e,u,m,cnt,v;
int viz[NMAX],viz2[NMAX];
void dfs(int u)
{
    viz[u]=1;
    for(int j=0;j<G[u].size();j++)
        if(!viz[G[u][j]])
    {
        dfs(G[u][j]);
    }
    st.push(u);
}

void dfs2(int u)
{
    viz2[u]=cnt;
    for(int j=0;j<T[u].size();j++)
        if(!viz2[T[u][j]])
    {
        dfs2(T[u][j]);
    }

}


int main()
{

    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>u>>v;
        G[u].push_back(v);
        T[v].push_back(u);
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
    {
        dfs(i);
    }
    while(!st.empty())
    {
        if(!viz2[st.top()])
        {
            cnt++;
            dfs2(st.top());
        }
        st.pop();
    }

    for(i=1;i<=n;i++)
        sol[viz2[i]].push_back(i);
    fout<<cnt<<endl;
    for(i=1;i<=cnt;i++)
    {
        for(j=0;j<sol[i].size();j++)
            fout<<sol[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}