Pagini recente » Cod sursa (job #1360555) | Cod sursa (job #280385) | Cod sursa (job #2592897) | Cod sursa (job #2117104) | Cod sursa (job #411561)
Cod sursa(job #411561)
#include<fstream>
#define Max 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int a[Max][Max],m,n,nrc,suc[Max],pred[Max];
void read()
{
int i,x,y;
fin>>n>>m;
for(i = 1; i <= m; i++)
{
fin>>x>>y;
a[x][y] = 1;
}
fin.close();
}
void df(int k)
{
int i;
suc[k] = nrc;
for(i = 1; i <= n; i++)
if(a[k][i] == 1 && suc[i] == 0)
df(i);
}
void df2(int k)
{
int i;
pred[k] = nrc;
for(i = 1; i <= n; i++)
if(a[i][k] == 1 && pred[i] == 0)
df2(i);
}
int main()
{
int i,j;
read();
nrc = 1;
for(i = 1; i <= n; i++)
{
if(suc[i] == 0)
{
suc[i] = nrc;
df(i);
df2(i);
for(j = 1; j <= n; j++)
if(suc[j] != pred[j])
suc[j] = pred[j] = 0;
nrc++;
}
}
fout<<nrc-1<<"\n";
int nr = 1;
for(i = 1; i <= nrc; i++)
{
for(j = 1; j <= n; j++)
if(suc[j] == nr)
fout<<j<<" ";
fout<<"\n";
nr = nr+1;
}
fout.close();
return 0;
}