Pagini recente » Cod sursa (job #1286506) | Cod sursa (job #2953295) | Cod sursa (job #86928) | Cod sursa (job #147694) | Cod sursa (job #1922782)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> A[100001];
vector <int> AT[100001];
int N;
int C[100001],V[100001], VT[100001];
int df1(int x){
vector <int> :: iterator it;
V[x] = 1;
for( it = A[x].begin(); it != A[x].end();it++ )
if( V[*it] == 0 )
df1(*it);
}
int df2(int x){
vector <int> :: iterator it;
VT[x] = 1;
for( it = AT[x].begin(); it != AT[x].end();it++ )
if( VT[*it] == 0 )
df2(*it);
}
int main()
{
int m, i, x, y, j, nrt;
f >> N;
f >> m;
for(i = 1; i <= m; i++){
f >> x >> y;
A[x].push_back(y);
AT[y].push_back(x);
}
nrt = 0;
for( i = 1; i <= N; i++ ){
if(C[i] == 0){
nrt++;
for(j = 1; j <= N; j++)
V[j] = VT[j] = 0;
df1(i);
df2(i);
for(j = 1; j <= N; j++)
if(V[j] == 1 && VT[j] == 1)
C[j] = nrt;
}
}
g << nrt << '\n';
for(i = 1; i <= nrt;i++){
for(j = 1; j <= N; j++)
if(C[j] == i)
g << j << " ";
g << '\n';
}
return 0;
}