Pagini recente » Cod sursa (job #1122072) | Cod sursa (job #1720808) | Cod sursa (job #1271620) | Cod sursa (job #749043) | Cod sursa (job #653567)
Cod sursa(job #653567)
#include<fstream>
#include<vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int N,M,nrc=1,suc[100010],pred[100010];
vector<int>A[100010],At[100010];
void Read()
{
int x,y,i;
in>>N>>M;
for(i = 1; i <= M; ++ i)
{
in >> x >> y;
A[x].push_back(y);
At[y].push_back(x);
}
}
void df_1(int nod)
{
int i;
suc[nod]=nrc;
for(i = 0; i < A[nod].size(); ++ i)
if(!suc[A[nod][i]])
df_1(A[nod][i]);
}
void df_2(int nod)
{
int i;
pred[nod]=nrc;
for(i = 0; i < At[nod].size(); ++ i)
if(!pred[At[nod][i]])
df_2(At[nod][i]);
}
int main()
{
int i,j;
Read();
for(i = 1; i <= N; ++ i)
if(!suc[i])
{
suc[i]=nrc;
df_1(i); df_2(i);
for(j = 1; j <= N; j++)
if(suc[j]!=pred[j])
suc[j]=pred[j]=0;
nrc ++;
}
out << nrc-1 << '\n';
for(i = 1; i < nrc; ++i)
{
for( j = 1; j <= N; ++j)
if(suc[j]==i) out << j << " ";
out << '\n';
}
}