Pagini recente » Cod sursa (job #268613) | Cod sursa (job #904392) | Cod sursa (job #1169990) | Cod sursa (job #2150839) | Cod sursa (job #2436922)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m;
int nrctc;
vector <int> ctc[100001];
vector <int> v[100001];
vector <int> inv[100001];
int viz[100001];
stack <int> stiva;
void DFS(int nod){
viz[nod] = 1;
for(int i = 0;i < v[nod].size();i++){
int vecin = v[nod][i];
if(!viz[vecin]){
DFS(vecin);
}
}
stiva.push(nod);
}
void DFS2(int nod){
viz[nod] = 2;
ctc[nrctc].push_back(nod);
for(int i = 0;i < inv[nod].size();i++){
int vecin = inv[nod][i];
if(viz[vecin] == 1){
DFS2(vecin);
}
}
}
int main() {
int i;
in >> n >> m;
for(i = 1;i <= m;i++){
int x,y;
in >> x >> y;
v[x].push_back(y);
inv[y].push_back(x);
}
for(i = 1;i<= n;i++){
if(!viz[i]){
DFS(i);
}
}
while(!stiva.empty()){
int nod = stiva.top();
if(viz[nod] == 1)
nrctc++,DFS2(nod);
stiva.pop();
}
out << nrctc << "\n";
for(i = 1;i <= nrctc;i++){
for(int j = 0;j < ctc[i].size();j++){
out << ctc[i][j] << " ";
}
out << "\n";
}
return 0;
}