Cod sursa(job #2765604)

Utilizator davidg0022Gatea David davidg0022 Data 28 iulie 2021 14:09:19
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

ifstream cin("componenteconexe.in");
ofstream cout("componenteconexe.out");
#define NLIM 100005
int n, m, cnt;
vector<int> G[NLIM];
vector<int> GT[NLIM];
vector<bool> V;
stack<int> S;
vector<int> Rez[NLIM];
void dfs(int nod){
    V[nod] = true;
    for(int i:G[nod])
        if(!V[i])
            dfs(i);
    S.push(nod);
}

void dfsGT(int nod){
    V[nod] = true;
    Rez[cnt].push_back(nod);
    for(int i:GT[nod])
        if(!V[i])
            dfsGT(i);
}

bool cmp(vector<int>a,vector<int>b){
    return a.at(0) < b.at(0);
}

void read(){
    cin >> n >> m;
    for (int x, y, i = 1; i <= m;i++)
        cin >> x >> y,
        G[x].push_back(y),
        GT[y].push_back(x);
    V = vector<bool>(n + 1, false);
    for (int i = 1; i <= n;i++)
        if(!V[i])
            dfs(i);
    V = vector<bool>(n + 1, false);
    while(!S.empty()){
        if(!V[S.top()])
            cnt++,
            dfsGT(S.top());
        S.pop();
    }
    cout << cnt << '\n';
    if(cnt){
        sort(Rez, Rez, cmp);
        for(vector<int> i:Rez)
            if(i.size()){
                sort(i.begin(),i.end());
                for(int j:i)
                    cout << j << ' ';
            cout << '\n';
            }
        
}
}


int main(){
    read();
    return 0;
}