Pagini recente » Cod sursa (job #123589) | Cod sursa (job #2037005) | Cod sursa (job #1247068) | Cod sursa (job #2866189) | Cod sursa (job #1790727)
#include <bits/stdc++.h>
using namespace std;
int N,M;
const int Nmax = 666013;
vector<vector<int>> G, Gt, ctc;
vector<int> crt;
stack<int> S;
bitset<Nmax> used;
void DFS(int k)
{
used[k] = 1;
for(auto it : G[k])
if(!used[it])
DFS(it);
S.push(k);
}
void DFST(int k)
{
used[k] = 1;
crt.push_back(k);
for(auto it : Gt[k])
if(!used[it])
DFST(it);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
cin.sync_with_stdio(false);
cin >> N >> M;
G.resize(N+1);
Gt.resize(N+1);
for(int i = 1; i <= M; ++i) {
int a,b;
cin >> a >> b;
G[a].push_back(b);
Gt[b].push_back(a);
}
for(int i = 1; i <= N; ++i)
if(!used[i])
DFS(i);
used = 0;
while(!S.empty()) {
int k = S.top(); S.pop();
if(used[k])
continue;
DFST(k);
ctc.push_back(crt);
crt.clear();
}
cout << ctc.size() << "\n";
for(auto it : ctc) {
sort(it.begin(), it.end());
for(auto jt : it)
cout << jt << " ";
cout << "\n";
}
return 0;
}