Cod sursa(job #2972306)

Utilizator divadddDavid Curca divaddd Data 29 ianuarie 2023 01:05:08
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define MAX 100002
using namespace std;
int n,m,x,y,st[MAX],low[MAX],id[MAX],inst[MAX],cnt,vf,nrcomp;
vector<int> v[MAX],comp[MAX];

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

void dfs(int nod){
    st[++vf] = nod;
    inst[nod] = 1;
    id[nod] = low[nod] = ++cnt;
    for(int vecin: v[nod]){
        if(id[vecin] == -1){
            dfs(vecin);
        }
        if(inst[vecin]){
            low[nod] = min(low[nod], low[vecin]);
        }
    }
    if(id[nod] == low[nod]){
        nrcomp++;
        while(1){
            comp[nrcomp].push_back(st[vf]);
            inst[st[vf]] = 0;
            low[st[vf]] = id[nod];
            vf--;
            if(st[vf+1] == nod){
                break;
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> x >> y;
        v[x].push_back(y);
    }
    memset(id, -1, sizeof(id));
    for(int i = 1; i <= n; i++){
        if(id[i] == -1){
            vf = 0;
            dfs(i);
        }
    }
    fout << nrcomp << "\n";
    for(int i = 1; i <= nrcomp; i++){
        for(int it: comp[i]){
            fout << it << " ";
        }
        fout << "\n";
    }
    return 0;
}