Pagini recente » Cod sursa (job #2434376) | Cod sursa (job #2045047) | Cod sursa (job #2158636) | Cod sursa (job #2285296) | Cod sursa (job #527909)
Cod sursa(job #527909)
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#define pb push_back
#define nmax 100005
/*
In acesta sursa se vede clar de ce trebuie facute anumite lucruri in algoritmul Kosaraju
Exista 3 situatii posibile
-ajungem intr-un nod=> poate fi din aceiasi componenta tare conexa cu nodu lde start
-nu ajungem intr-un nod => nu puteam ajunge la el in graful G
=> nodul nu poate face parte din aceiasi componenta conexa
Dar daca avem o muchie inversa intre u(din componeta conexa Y ) si v?
Este clar ca ne afla in situatia 2 pentru graful G dar in graful muchia va fi de la u la v
si daca pormin din componenta lui u(Y) atunci il vom include si pe v care nu face parte din Y.
Din acest motiv componetele conexe trebuie puse in ordinea inversa in care au fost gasite
ca sa nu ajungem din v la u
Nodurile aceiasi componeta pot fi lasate in ordinea in care sunt gasite.
*/
struct nod{
int lg;};
vector<nod> G[nmax];
vector<nod> TG[nmax];
vector<int> ans[nmax];
vector<int> q[nmax];
ofstream fout("ctc.out");
int N,M,viz[nmax],nr,postord[nmax],E;
void DFS(int u)
{
if(viz[u]) return;
viz[u]=1;
//postord[++nr]=u;
q[E].push_back(u);
vector<nod>::iterator it;
for(it=G[u].begin();it<G[u].end();it++)
{
DFS(it->lg);
}
}
void DFS2(int u)
{
if(!viz[u]) return;
viz[u]=0;
vector<nod>::iterator it;
for(it=TG[u].begin();it<TG[u].end();it++)
{
DFS2(it->lg);
}
ans[nr].pb(u);
}
void solve()
{
int i,j;
for(i=1;i<=N;i++)
if(!viz[i])
{ E++;
DFS(i);
}
nr=0;
/*for(i=1;i<=N;i++)
{
cout<<postord[i]<<" ";
}*/
for(i=E;i>=1;i--)
{
for(j=0;j<q[i].size();j++)
{
// cout<<q[i][j]<<" ";
if(viz[q[i][j]])
{nr++;
DFS2(q[i][j]);
}
}
//cout<<"\n";
}
fout<<nr<<"\n";
for(i=1;i<=nr;i++)
{
for(j=0;j<ans[i].size();j++)
fout<<ans[i][j]<<" ";
fout<<"\n";
}
}
void cit()
{
ifstream fin("ctc.in");
int i,x,y;
fin>>N>>M;
for(i=1;i<=M;i++)
{
fin>>x>>y;
G[x].pb((nod){y});
TG[y].pb((nod){x});
}
fin.close();
}
int main()
{
cit();
solve();
fout.close();
return 0;
}