Cod sursa(job #2360822)

Utilizator CryshanaGanea Carina Cryshana Data 2 martie 2019 10:28:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int N = 100001;
vector <int> s[N];
vector <int> p[N];
vector <int> ctc[N];
int n, m, nr = 0, st[N];
bool vizs[N], vizp[N];
ifstream in ("ctc.in");
ofstream out ("ctc.out");

void citire()
{
    in >> n >> m;
    int x, y;
    for ( int i = 0; i < m; i++ )
    {
        in >> x >> y;
        s[x].push_back(y);
        p[y].push_back(x);
    }
}

void dfss( int x )
{
    vizs[x] = true;
    for ( int i = 0; i < s[x].size(); i++ )
    {
        int y = s[x][i];
        if ( !vizs[y] )
        {
            dfss(y);
        }
    }
    st[++nr] = x;
}

void dfsp( int x, int nc )
{
    ctc[nc].push_back(x);
    vizp[x] = true;
    for ( int i = 0; i < p[x].size(); i++ )
    {
        int y = p[x][i];
        if ( !vizp[y] )
        {
            dfsp(y, nc);
        }
    }
}

int main()
{
    citire();
    for ( int i = 1; i <= n; i++ )
    {
        if ( !vizs[i] )
        dfss(i);
    }
    int nc = 0;
    for ( int i = n; i > 0; i-- )
    {
        if ( !vizp[st[i]] )
        {
            nc++;
            dfsp(st[i], nc);
        }
    }
    out << nc << "\n";
    for( int i = 1; i <= nc; i++ )
    {
        for ( int j = 0; j < ctc[i].size(); j++ )
        {
            out << ctc[i][j] << " ";
        }
        out << "\n";
    }
    return 0;
}