Cod sursa(job #3275707)

Utilizator Mateixx1Trandafir matei Mateixx1 Data 11 februarie 2025 16:49:35
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX=100010;
int N,M,nrc;
vector<int>G[NMAX],GT[NMAX],
       CTC[NMAX], ///CTC[i]=lista nodurilor din a i-a c.t.c
       Post;///Lista nodurilor lui G i oridnea finalizarii acestora in pacurgerea DFS
bool viz[NMAX];

void citire() {
    int x,y;
    f>>N>>M;
    while(M--) {
        f>>x>>y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
}

void dfs(int vf) {
    viz[vf]=1;///+
    for(int x:G[vf]) {
        if(viz[x]==0) {
            dfs(x);
        }
    }
    Post.push_back(vf);///s-a finalizat parcurgerea din vf
}

void dfsGT(int vf) {
    viz[vf]=0;///-
    CTC[nrc].push_back(vf);
    for(int x:GT[vf]) {
        if(viz[x]==1) {
            dfsGT(x);
        }
    }
}

void componente() { ///Algoritmul Kosaraju-Sharir
    int i;
    for(i=1; i<=N; ++i) {
        if(viz[i]==0) {
            dfs(i);
        }
    }
    for(i=Post.size()-1; i>=0; i--) {
        if(viz[Post[i]]==1) {
            nrc++;
            dfsGT(Post[i]);
        }
    }
}

void afisare() {
    g<<nrc<<'\n';
    for(int i=1; i<=nrc; i++) {
        for(int x:CTC[i]) {
            g<<x<<' ';
        }
        g<<'\n';
    }
}

int main() {
    citire();
    componente();
    afisare();
    f.close();
    g.close();
    return 0;
}