Pagini recente » Cod sursa (job #23092) | Cod sursa (job #292488) | Cod sursa (job #2517066) | Cod sursa (job #1044555) | Cod sursa (job #2928831)
//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>
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++) {
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;
}