Cod sursa(job #1922688)

Utilizator gbibBacotiu Gabi gbib Data 10 martie 2017 18:26:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");

int viz[100004],inc[100004];
vector <int> comp[100004],v[100004],t[100004];
stack <int> st;
int nrcomp;
void dfs(int nod)
{
    int i,lg;
    lg=v[nod].size();
    viz[nod]=1;
    for(i=0;i<lg;i++)
        if(!viz[v[nod][i]])
            dfs(v[nod][i]);
    st.push(nod);
}

void dfst(int nod)
{
    int i,lg;
    lg=t[nod].size();
    inc[nod]=1;
    for(i=0;i<lg;i++)
        if(!inc[t[nod][i]])
            dfst(t[nod][i]);
    comp[nrcomp].push_back(nod);
}

int main()
{
    int n,m,i,x,y,j;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y;
        v[x].push_back(y);
        t[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    while(!st.empty())
    {
        int nod=st.top();
        if(!inc[nod])
        {
            ++nrcomp;
            dfst(nod);
        }
        st.pop();
    }
    out<<nrcomp<<'\n';
    for(i=1;i<=nrcomp;i++)
    {
        int lg=comp[i].size();
        for(j=0;j<lg;j++)
            out<<comp[i][j]<<" ";
        out<<'\n';
    }

    return 0;

}