Pagini recente » Cod sursa (job #1805965) | Clasament 27-03-2017_todo | Cod sursa (job #829930) | Cod sursa (job #781654) | Cod sursa (job #2795859)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
class graf_orientat
{
int n, m; //n = nr. varfuri m = nr. arce
public:
vector <int> lista[100001]; //in acest mod va fi stocat graful (lista adiacenta)
vector <int> lista1[100001];
stack <int> S;
int contor;
vector <int> ctc[100001];
bool vizitate[100001];
graf_orientat(int, int); //constructor
void construire_graf_orientat_ctc();
void refacere_viz();
void dfs_1(int);
void dfs_compTC(int);
};
graf_orientat :: graf_orientat(int n, int m)
{
this -> n = n;
this -> m = m;
}
void graf_orientat :: construire_graf_orientat_ctc()
{
for(int i = 0; i < m; i ++) //parcurgem arcele
{
int u, v;
in >> u >> v; //citim varfurile intre care exista arc
lista[u].push_back(v); //lista[u] = varfurile unde se poate ajunge din u
lista1[v].push_back(u); //lista1[v] = varfurile din care se poate ajunge in v
}
}
void graf_orientat :: refacere_viz() //se marcheaza vectorul de vizitate cu 0
{
for(int i = 1; i <= n; i ++)
vizitate[i]=0;
}
void graf_orientat :: dfs_1(int nod) //parcurgere plecand din nod care este neviz.
{
vizitate[nod] = 1; //marcheaza nodul ca vizitat
for(int i = 0; i < lista[nod].size(); i ++) //parcurgem lista de vecini a lui nod
{
if(vizitate[lista[nod][i]] == 0) //daca vecinul i al lui nod nu a fost vizitat
{
dfs_1(lista[nod][i]); //apelam recursiv dfs pentru vecinul respectiv
}
}
S.push(nod); //la intoarcerea din apelul recursiv, adaugam nodul in stiva
//in stiva se realizeaza un fel de sortare topologica, daca privim graful condensat, dpdv fiind aciclic
//(nodurile sunt grupate pe comp. tare conexe)
}
void graf_orientat :: dfs_compTC(int nod) //parcurgere plecand spre nod
{
vizitate[nod] = 2;
ctc[contor].push_back(nod); //pune nodul respectiv in vectorul rezultat si il marcheaza ca a fost vizitat de 2 ori
for(int i = 0; i < lista1[nod].size(); i ++) //pt. fiecare nod i din care se poate ajunge in nod
{
if(vizitate[lista1[nod][i]] == 0) //daca nu a fost vizitat
{
dfs_compTC(lista1[nod][i]); //apelam recursiv pentru i
}
}
}
int main()
{
int n, m;
in >> n >> m; //se citesc nr. de noduri, nr. de muchii
graf_orientat G(n, m); //se apeleaza constructorul
G.construire_graf_orientat_ctc(); //se apeleaza functia de construire a grafului
//CTC-Kosoraju
//pune in stiva nodurile din parcurgerea dfs
for(int j = 1; j <= n; j ++)
{
if(G.vizitate[j] == 0)
{
G.dfs_1(j);
}
}
G.refacere_viz();
while(!G.S.empty()) //daca stiva nu e goala
{
//scoate din stiva elemente pana cand gaseste unul neviz.
int temp = G.S.top(); //salveaza top-ul stivei in temp
G.S.pop(); //scoate primul elem. din stiva
if(G.vizitate[temp] == 0) //daca nodul nu a fost viz. => el face parte dintr-o nou comp. tare conexa
{
G.contor++; //contorizam comp.
G.dfs_compTC(temp); //generam comp. tare conexa prin parcurgere dfs in traspusa grafului
}
}
out << G.contor << "\n";
for(int i = 1; i <= G.contor; i ++)
{
for (int j = 0; j < G.ctc[i].size(); j ++)
{
out << G.ctc[i][j] << " ";
}
out<<"\n";
}
}