Cod sursa(job #2175581)

Utilizator filip.mihalutMihalut Filip filip.mihalut Data 16 martie 2018 17:56:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define Nmax 100005

using namespace std;

ifstream f ("ctc.in");
ofstream g ("ctc.out");

vector < int > v1[Nmax];
vector < int > v2[Nmax];
vector < int > v3[Nmax];

int x,y,n,m,i,j , viz[Nmax],nrcomp,l;
stack < int > st;

inline void read()
{
    f >> n >> m;
    for(i = 1;i <= m;i++)
    {
        f >> x >> y;
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
}

inline void dfs1(int nod)
{
    viz[nod] = 1;
    for(int i = 0,l = v1[nod].size(); i < l;i++)
        if(viz[v1[nod][i]] == 0)
           dfs1(v1[nod][i]);

    st.push(nod);
}

inline void dfs2(int nod)
{
    viz[nod] = -1;
    for(int i = 0,l = v2[nod].size(); i < l;i++)
        if(viz[v2[nod][i]] != -1)
           dfs2(v2[nod][i]);

    v3[nrcomp].push_back(nod);
}

void afisare()
{
    g << nrcomp << '\n';
    for(i = 1;i <= nrcomp;i++)
    {
        for(j = 0,l = v3[i].size();j < l;j++)
            g << v3[i][j] << " ";
        g << '\n';
    }
}

int main()
{
    read();
    for(i = 1;i <= n;i++)
        if(not viz[i])
            dfs1(i);

    while(not st.empty())
    {
        if(viz[st.top()] == -1)
        {
            st.pop();
            continue;
        }
        nrcomp++;
        dfs2(st.top());
        st.pop();
    }

    afisare();
    return 0;
}