Cod sursa(job #2214602)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 19 iunie 2018 14:28:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

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

vector <int> G1[100003], G2[100003];

vector <int> Q;

vector <int> sol[100003];

int ntc=0;

int n, m, i, x, y;

bool sel1[100003], sel2[100003];

void df1 (int x)
{
    int i, y;

    sel1[x]=true;

    for(i=0; i<G1[x].size(); i++) {
        y=G1[x][i];
        if(!sel1[y])
            df1(y);
    }

    Q.push_back(x);
}

void df2 (int x)
{
    int i, y;

    sel2[x]=true;

    for(i=0; i<G2[x].size(); i++) {
        y=G2[x][i];
        if(!sel2[y])
            df2(y);
    }

    sol[ntc].push_back(x);
}

int main()
{
    f>>n>>m;

    for(i=1; i<=m; i++) {
        f>>x>>y;
        G1[x].push_back(y);
        G2[y].push_back(x);
    }

    for(i=1; i<=n; i++)
        if(!sel1[i])
            df1(i);

    reverse (Q.begin(), Q.end());

    for(i=0; i<n; i++)
        if(!sel2[Q[i]]) {
            ntc++;
            df2(Q[i]);
        }

    g<<ntc<<'\n';

    for(i=1; i<=ntc; i++) {
        for(int j=0; j<sol[i].size(); j++)
            g<<sol[i][j]<<' ';

        g<<'\n';
    }

    return 0;
}