Pagini recente » Cod sursa (job #1183806) | Cod sursa (job #1371527) | Cod sursa (job #1109456) | Cod sursa (job #2466794) | Cod sursa (job #2936233)
#include <bits/stdc++.h>
#define N 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
///complexitate n^2
int n, m;
vector <int> gr[N]; /// graful cu liste de adiacenta
vector <int> grT[N]; /// graful transpus cu liste de adiacenta
bool viz1[N]; /// pentru graful initial
bool viz2[N]; /// pentru graful transpus
stack <int> S; /// stiva pentru memorarea nodurilor in ordinea timpilor de final
vector <int> componente[N];
void Citire()
{
fin >> n >> m; //citesc nr noduri, nr muchii
for(int i = 1; i <= m; ++i)
{
int x, y;
fin >> x >> y; //citesc muchiile
gr[x].push_back(y); //creez lista de adiacenta pt graful initial
}
}
void Gr_Transpus()
{
for(int i = 1; i <= n; ++i)
for(auto j : gr[i])
grT[j].push_back(i); //creez graful transpus
}
void DFS(int s)
{
viz1[s] = 1;
for(auto i : gr[s])
if(!viz1[i])
DFS(i);
S.push(s);
}
void ParcurgereGrafInitial()
{
for(int i = 1; i <= n; ++i)
if(!viz1[i])
DFS(i);
}
void DFST(int s, int ct)
{
viz2[s] = 1;
componente[ct].push_back(s); /// salvam nodurile pentru afisarea ulterioara
for(auto i : grT[s])
if(!viz2[i])
DFST(i, ct);
}
void CTC()
{
int ct_ctc = 0;
while(!S.empty()) //cat timp nu e goala stiva cu parcurgerea DFS pe graful initial
{
int varf = S.top(); //preiau varful stivei
S.pop(); //il elimin
if(!viz2[varf]) //daca nu a fost vizitat in parcurgerea pe graful transpus
{
ct_ctc++; //cresc contor comp tare conexe
DFST(varf, ct_ctc); //parcurg din acel varf
}
}
/// afisare
fout << ct_ctc << "\n";
for(int i = 1; i <= ct_ctc; ++i)
{
for(auto j:componente[i])
fout << j << " ";
fout << "\n";
}
}
int main()
{
Citire();
Gr_Transpus();
ParcurgereGrafInitial();
CTC();
return 0;
}