Pagini recente » Cod sursa (job #1605791) | Monitorul de evaluare | Cod sursa (job #1262939) | Cod sursa (job #2387912) | Cod sursa (job #2928750)
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
vector<vector<int>> la(100001);
vector<vector<int>> transpusa(100001);
vector<bool> viz(100001);
vector<int> stack;
int index = 0;
map<int, vector<int>> compConexe;
void DFS(int node){
viz[node] = true;
for(auto iter: la[node]){
if(!viz[iter]){
DFS(iter);
}
}
stack.push_back(node);
}
void dfsTransp(int node){
viz[node] = true;
for(auto iter: transpusa[node]){
if(!viz[iter]){
dfsTransp(iter);
}
}
compConexe[index].push_back(node);
}
int main() {
f>>n>>m;
for(int i = 0; i < m; i++){
int v1, v2;
f>>v1>>v2;
la[v1].push_back(v2);
transpusa[v2].push_back(v1);
}
for(int i = 0; i < n; i++){
if(!viz[i]){
DFS(i);
}
}
viz = vector<bool> (n+1, false);
for(vector<int>:: reverse_iterator iter = stack.rbegin(); iter != stack.rend(); iter++){
if(!viz[*iter]){
dfsTransp(*iter);
index++;
}
}
index--;
g<<index<<endl;
for(auto iter: compConexe){
if(iter.first != index){
for(auto iter2: iter.second){
g<<iter2<<" ";
}
g<<endl;
}
}
return 0;
}