Pagini recente » Cod sursa (job #154306) | Cod sursa (job #1070325) | Cod sursa (job #2088234) | Cod sursa (job #1150921) | Cod sursa (job #3257090)
#include <iostream>
#include <fstream>
using namespace std;
int n,m,f[100005],v[100005],nrc,j=1;
bool G[1000][1000],GT[1000][1000];
void citire()
{
int x,y;
ifstream f("ctc.in");
f>>n>>m;
for(int i=1;i<=m;i++)
{
f>>x>>y;
G[x][y]=1;
GT[y][x]=1;
}
}
void dfs(int k,bool M[1000][1000],bool g)
{
if(g)
v[k]=true;
else
v[k]=nrc;
for(int i=1;i<=n;i++)
if(v[i]==0&&M[k][i])
dfs(i,M,g);
if(g)
{
f[j]=k;
j++;
}
}
void init()
{
for(int i=1;i<=n;i++)
v[i]=0;
}
void Kosaraju()
{
for(int i=1;i<=n;i++)
if(v[i]==0)
dfs(i,G,1);
init();
for(int i=n;i>=1;i--)
if(!v[f[i]])
{
nrc++;
dfs(f[i],GT,0);
}
}
void afisare()
{
ofstream g("ctc.out");
g<<nrc<<endl;
for(int i=1;i<=nrc;i++)
{
for(int j=1;j<=n;j++)
if(v[j]==i)
g<<j<<" ";
g<<endl;
}
}
int main()
{
citire();
Kosaraju();
afisare();
return 0;
}