Pagini recente » Cod sursa (job #1424119) | Cod sursa (job #3125783) | Cod sursa (job #576470) | Cod sursa (job #1713717) | Cod sursa (job #3257095)
#include <iostream>
#include <fstream>
using namespace std;
int long n,m,f[100005],v[100005],nrc,j=1;
bool G[1005][1005],GT[1005][1005];
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 dfsG(int k)
{
v[k]=true;
for(int i=1;i<=n;i++)
{
if(v[i]==0&&G[k][i])
dfsG(i);
}
f[j]=k;
j++;
}
void dfsGT(int k)
{
v[k]=nrc;
for(int i=1;i<=n;i++)
if(v[i]==0&>[k][i])
dfsGT(i);
}
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)
dfsG(i);
init();
for(int i=n;i>=1;i--)
if(v[f[i]]==0)
{
nrc++;
dfsGT(f[i]);
}
}
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;
}