Pagini recente » Termeni si conditii de utilizare a site-ului infoarena | Cod sursa (job #2646987) | Cod sursa (job #2977584) | Cod sursa (job #1931346) | Cod sursa (job #2928864)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, y, x, viz[100000], nrComp;
vector<vector<int>> lista, transp, comp;
vector<int> s, v;
void dfs1(int x){
viz[x] = 1;
for(auto i: lista[x])
if(!viz[i]) dfs1(i);
s.push_back(x);
}
void dfs2(int x){
viz[x] = 0;
comp[nrComp].push_back(x);
for(auto i: transp[x])
if(viz[i])
dfs2(i);
}
int main(){
fin>>n>>m;
lista = transp = vector<vector<int>> (n);
for(int i=0;i<m;i++) {
fin>>x>>y;
lista[x-1].push_back(y-1);
transp[y-1].push_back(x-1);
}
for(int i=0;i<n;i++)
if(!viz[i]) dfs1(i);
while(!s.empty()){
x = s.back();
s.pop_back();
if(viz[x]){
comp.push_back(v);
dfs2(x);
nrComp++;
}
}
fout<<nrComp<<endl;
for(auto v: comp){
for(auto i: v) fout<<i + 1<<" ";
fout<<endl;
}
}