Cod sursa(job #2560976)

Utilizator Robys01Robert Sorete Robys01 Data 28 februarie 2020 13:52:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>
#define NMAX 100001
#define MMAX 200001
using namespace std;

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

int n, m, nr, vf[MMAX], urm[MMAX], last[NMAX];
int nrt, vft[MMAX], urmt[MMAX], lastt[NMAX];
int top[NMAX], nrtop, nrc;
bitset < NMAX > viz;
vector < int > answer[NMAX];

void adauga(int from, int to)
{
    vf[++nr] = to;
    urm[nr] = last[from];
    last[from] = nr;
}

void adaugat(int from, int to)
{
    vft[++nrt] = to;
    urmt[nrt] = lastt[from];
    lastt[from] = nrt;
}


void citire()
{
    fin>>n>>m;
    for(int x, y, i=1; i<=m; i++)
    {
        fin>>x>>y;
        adauga(x, y);
        adaugat(y, x);

    }

}

void dfs(int nod)
{
    viz[nod] = 1;

    for(int k = last[nod]; k; k = urm[k])
        if(viz[ vf[k] ] == 0)
            dfs(vf[k]);

    top[++nrtop] = nod;

}

void dfst(int nod)
{
    viz[nod] = 1;
    answer[nrc].push_back(nod);
    for(int k = lastt[nod]; k; k = urmt[k])
        if(viz[ vft[k] ] == 0)
            dfst(vft[k]);
}


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

    viz = 0;

    for(int i = nrtop; i>0; i--)
    {
        if(!viz[ top[i] ])
        {
            nrc++;
            dfst(top[i]);
        }

    }
    fout<<nrc<<'\n';
    for(int i=1; i<=nrc; i++)
    {
        for(auto a : answer[i])
            fout<<a<<' ';
        fout<<'\n';

    }

    return 0;
}