Pagini recente » Cod sursa (job #2537605) | Cod sursa (job #927002) | Cod sursa (job #2658471) | Cod sursa (job #575218) | Cod sursa (job #519172)
Cod sursa(job #519172)
//Kosaraju
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 100005
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
vector<int> G[MAX],GT[MAX];
vector<int> v[MAX];
vector<int> p;
vector<int> tip;
stack<int>S;
int nr;
void DFP(int nod)
{
int i,x;
p[nod]=true;
x=G[nod].size();
for(i=0;i<x;i++)
if(!p[G[nod][i]]) DFP(G[nod][i]);
S.push(nod);
}
void DFM(int nod)
{
int i,x;
tip[nod]=nr;
x=GT[nod].size();
for(i=0;i<x;i++)
if(!tip[GT[nod][i]]) DFM(GT[nod][i]);
}
int main()
{
int n,m,x,y,i,j;
fi>>n>>m;
for(i=1;i<=m;i++)
{
fi>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
p.resize(n+1);
p.assign(p.size(),false);
for(i=1;i<=n;i++)
if(p[i]==false)
DFP(i);
tip.resize(n+1);
tip.assign(tip.size(),0);
for(;!S.empty();S.pop())
if(!tip[S.top()])
{
nr++;
DFM(S.top());
}
fo<<nr<<"\n";
for(i=1;i<=n;i++) v[tip[i]].push_back(i);
for(i=1;i<=nr;i++)
{
x=v[i].size();
for(j=0;j<x;j++) fo<<v[i][j]<<" ";
fo<<"\n";
}
}