Cod sursa(job #2390514)

Utilizator moltComan Calin molt Data 28 martie 2019 10:10:54
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
using namespace std;

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

vector<int> v[200005];
vector<int> vt[200005];
stack<int> st;
vector<int> sol[200005];
int n,m,x,y;
int fr[200005];
int nrct;

void dfs1(int nod)
{
    fr[nod] = 1;
    for (vector<int> :: iterator it = v[nod].begin(); it != v[nod].end();++it)
        if (fr[*it] == 0)
          dfs1(*it);
    st.push(nod);
}

void dfs2(int nod)
{
    fr[nod] = nrct;
    for (vector<int> :: iterator it = vt[nod].begin(); it != vt[nod].end();++it)
        if (fr[*it] == 0)
           dfs2(*it);
    sol[nrct].push_back(nod);
}

int main()
{
    in>>n>>m;
    for (int i = 1;i <= m;++i)
    {
        in>>x>>y;
        v[x].push_back(y);
        vt[y].push_back(x);
    }
    for (int i = 1;i <= n;++i)
       if (fr[i] == 0) dfs1(i);
    for (int i = 1;i <= n;++i) fr[i] = 0;

    while (!st.empty())
    {
        int x = st.top();
        st.pop();
        if (fr[x]) continue;
        ++nrct;
        dfs2(x);
    }
    out<<nrct<<"\n";
    for (int i = 1;i <= nrct;++i)
    {
        for (vector<int> :: iterator it = sol[i].begin(); it != sol[i].end();++it)
             out<<*it<<" ";
        out<<"\n";
    }
    return 0;
}