Cod sursa(job #2562753)

Utilizator rusu.ralucaRusu Raluca rusu.raluca Data 29 februarie 2020 17:48:24
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <stack>
#include <cmath>

#define MAXN 100008

using namespace std;

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

int n, m, soll;
int used[MAXN];
vector<int> g1[MAXN],g2[MAXN],sol[MAXN];
stack<int> s;

void dfs(int nod){
    used[nod] = 1;
    for(int i = 0; i < g1[nod].size(); i++)
        if(!used[g1[nod][i]])
            dfs(g1[nod][i]);
    s.push(nod);
}
void dfs2(int nod, int nr){
    sol[nr].push_back(nod);
    used[nod] = 1;
    for(int i = 0; i < g2[nod].size(); i++)
        if(!used[g2[nod][i]])
            dfs2(g2[nod][i], nr);
}

void Kosarju(){
    for(int i = 1; i <= n; i++)
        if(!used[i])
            dfs(i);

    memset(used,0,sizeof(used));

    for(int i = 1; i <= n; i++){
        int x = s.top();
        if(!used[s.top()]){
            soll++;
            dfs2(s.top(),soll);
        }
        s.pop();
    }
    out << soll <<'\n';
    for(int i = 1; i <= soll; i++){
        for(int j = 0; j < sol[i].size(); j++)
            out << sol[i][j] <<" ";
        out << '\n';
    }
}

int main(){
    in >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        in >> x >> y;
        g1[x].push_back(y);
        g2[y].push_back(x);
    }
    Kosarju();
    return 0;
}