Cod sursa(job #2928850)

Utilizator bbia17Baicoianu Bianca bbia17 Data 23 octombrie 2022 23:08:23
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
//Folosim algoritmul lui Kosaraju, urmând pașii:
//
//determinăm graful transpus GT
//parcurgem în adâncime graful și determinăm pentru fiecare nod x timpul de finalizare f[x]
//parcurgem în adâncime graful transpus GT, dar considerăm nodurile în ordinea descrescătoarea timpilor de finalizare
//nodurile din arborii de parcurgere obținuți reprezintă câte o componentă tare conexă
//
// Complexitatea este O(n + m)

#include    <fstream>
#include    <iostream>
#include    <vector>
#include <bits/stdc++.h>
using namespace std;

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

vector<int> sol;
vector<int> G[5001],GT[5001],CTC[5001];

int n, m, contor;

int v[5001];

//functie de citire; se citesc intai numarul de noduri(n)
//și numarul de muchii(m)
void citire()
{
    f >> n >> m;
    //in continuare citim din fisier lista de muchii
    for(int i = 1; i <= m; i++)
    {
        int a,b;
        f >> a >> b;
        G[a].push_back(b); // Construim graful G
        GT[b].push_back(a); // Construim transpusa grafului G
    }
}

void dfs(int nod)
{
    v[nod] = 1;
    for(int i = 0; i < G[nod].size(); i++) {
        if(!v[G[nod][i]])
            dfs(G[nod][i]);
    }
    sol.push_back(nod);
}

void dfsGT(int nod)
{
    v[nod] = 2;
    CTC[contor].push_back(nod);
    for(int i = 0; i < GT[nod].size(); i++) {
        if(v[GT[nod][i]] == 1)
            dfsGT(GT[nod][i]);
    }
}

//functie de afisare a numarului de CTC,
//apoi a acestor componente retinute in vectorul CTC


void afisare()
{
    g << contor <<endl;
    for(int i = 1; i <= contor; i++) {
        sort(CTC[i].begin(), CTC[i].end());
        for(int j = 0; j < CTC[i].size(); j++)
            g << CTC[i][j] <<" ";
        g<<endl;
    }
}
int main()
{
    citire();
    for(int i = 1;i <= n; i++)
        if(!v[i])
            dfs(i);

    for(int i = sol.size()-1; i > 0; i--){
        if(v[sol[i]] == 1){
            contor++;
            dfsGT(sol[i]);
        }
    }

    afisare();
    return 0;
}