Pagini recente » Cod sursa (job #948706) | Cod sursa (job #2419899) | Cod sursa (job #1758576) | Cod sursa (job #869328) | Cod sursa (job #2927383)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
//Rezolvare: algoritmul lui Kosaraju
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m;
vector <int> l[100001], li[100001], ctc[100001];
int viz[100001], inc, nr;
stack <int> st; //stiva in care adaugam nodurile dupa dfs
void dfs(int nod)
{
viz[nod]=1;
for(int i=0; i<l[nod].size(); i++)
{
if(viz[l[nod][i]]==0)
{
dfs(l[nod][i]);
}
}
st.push(nod); //adaugam in stiva nodul curent dupa ce i-am parcurs urmasii in dfs
}
void dfsi(int nod, int nr) //dfs pt graful invers
{
viz[nod]=2; //e viz in dfs invers
ctc[nr].push_back(nod); //adaug nodul in ctc curenta (nr)
for(int i=0; i<li[nod].size(); i++)
{
if(viz[li[nod][i]]==1) //daca e deja vizitat dupa dfs
{
dfsi(li[nod][i], nr);
}
}
}
int main()
{
in>>n>>m;
int x, y;
for(int i=1; i<=m; i++)
{
in>>x>>y;
l[x].push_back(y); //adaugam in lista de adiacenta
li[y].push_back(x); //adaugam in lista de adiacenta a grafului invers
}
for(int i=1; i<=n; i++)
{
if(viz[i]==0)
dfs(i);
}
while(st.empty()==false)
{
int crt=st.top(); //ultimul elem pus in stiva dupa dfs
if(viz[crt]==1)
{
nr++; //creste nr de componente conexe (nodul crt nu e in ctc curenta)
dfsi(crt, nr);
}
st.pop(); //scot elem crt din stiva
}
out<<nr<<"\n";
for(int i=1; i<=nr; i++)
{
for(int j=0; j<ctc[i].size(); j++)
out<<ctc[i][j]<<" ";
out<<"\n";
}
return 0;
}