Pagini recente » Cod sursa (job #670090) | Cod sursa (job #1123353) | Cod sursa (job #1525072) | Cod sursa (job #411895) | Cod sursa (job #2492275)
#include <bits/stdc++.h>
using namespace std;
vector <int> v[100001],inv[100001];
stack <int> stiva;
vector <int> componente[100001];
int viz[100001];
void DFS(int nod){
viz[nod] = 1;
for(auto x : v[nod]){
if(!viz[x])
DFS(x);
}
stiva.push(nod);
}
int nrctc;
void DFS1(int nod){
viz[nod] = 2;
componente[nrctc].push_back(nod);
for(auto x : inv[nod]){
if(viz[x] == 1){
DFS1(x);
}
}
}
int main()
{
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int i,n,m;
cin >> n >> m;
for(i = 1;i <= m;i++){
int x,y;
cin >> x >> y;
v[x].push_back(y);
inv[y].push_back(x);
}
for(i = 1;i <= n;i++){
if(!viz[i]){
DFS(i);
}
}
nrctc = 0;
while(stiva.size()){
i = stiva.top();
stiva.pop();
if(viz[i] == 1){
nrctc++;
DFS1(i);
}
}
cout << nrctc << "\n";
for(i = 1;i <= nrctc;i++){
for(auto x : componente[i])
cout << x << " ";
cout << "\n";
}
return 0;
}