Pagini recente » Cod sursa (job #2069507) | Cod sursa (job #81236) | Cod sursa (job #1523045) | Cod sursa (job #1877429) | Cod sursa (job #2964360)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<vector<int> > g, gt;
vector<bool> v;
vector<int> s;
int n, m, t[100001];
void dfs(int k) {
v[k] = 1;
for ( auto x : g[k] ) {
if ( !v[x] ) dfs(x);
}
s.push_back(k);
}
void dfs1(int k, int ct) {
v[k] = 1;
for ( auto x : gt[k] ) {
if ( !v[x] ) dfs1(x, ct);
}
t[k] = ct;
}
int main()
{
int i, x, y, cnt = 0;
fin >> n >> m;
g = gt = vector<vector<int> > ( n + 1 );
for ( i = 1; i <= m; ++i ) {
fin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
v = vector<bool> (n+1, 0);
for ( i = 1; i <= n; ++i ) {
if ( !v[i] ) dfs(i);
}
v = vector<bool> (n+1, 0);
for ( i = s.size() - 1; i >= 0; --i ) {
if ( !v[s[i]] ) {
cnt++;
dfs1(s[i], cnt);
}
}
fout << cnt << '\n';
for ( i = 1; i <= cnt; ++i ) {
for ( int j = 1; j <= n; ++j ) {
if ( t[j] == i ) fout << j << " ";
}
fout << '\n';
}
return 0;
}