Pagini recente » Cod sursa (job #2543712) | Cod sursa (job #151895) | Cod sursa (job #2834200) | Cod sursa (job #2161368) | Cod sursa (job #2793477)
#include <bits/stdc++.h>
#include<fstream>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<algorithm>
std::ifstream f("ctc.in");
std::ofstream fg("ctc.out");
int n, m, a, b;
class graf{
public:
int n, m;
graf(int n, int m);
std::vector<std::vector<int> > lista;
std::vector<int> viz;
std::vector<int> low;
std::vector<int> membru;
std::deque<int> st;
std::vector< std::vector<int> > componente;
int nr_comp_conex = 0;
void new_lista( int nod1, int nod2);
void dfs(int nod);
void comp_conex();
};
graf::graf(int n, int m) {
this->n = n;
this->m = m;
std::vector<int> v;
for(auto i = 0 ; i<=n ; i++){
viz.push_back(-1);
low.push_back(-1);
membru.push_back(0);
lista.push_back(v);
}
}
void graf::new_lista(int nod1, int nod2){
lista[nod1].push_back(nod2);
//lista[nod2].push_back(nod1);
}
void graf::dfs(int nod){
static int cnt = 0;
viz[nod] = ++cnt;
low[nod] = cnt;
st.push_back(nod);
membru[nod] = 1;
for( auto i = lista[nod].begin(); i != lista[nod].end(); i++) {
if (viz[*i] == -1) {
dfs(*i);
low[nod] = fmin(low[nod], low[*i]);
} else if (membru[*i] == 1) {
low[nod] = fmin(low[nod], viz[*i]);
}
}
int aux = 0;
if(low[nod] == viz[nod]){
std::vector<int>v;
componente.push_back(v);
while(st.back() != nod){
aux = st.back();
//std::cout<< aux<<" ";
componente[nr_comp_conex].push_back(aux);
membru[aux] = 0;
st.pop_back();
}
aux = st.back();
//std::cout<< aux<<"\n ";
componente[nr_comp_conex].push_back(aux);
membru[aux] = 0;
st.pop_back();
++nr_comp_conex;
}
}
void graf::comp_conex(){
for(int i = 0 ; i< n ; i++){
if(viz[i] == -1) dfs(i);
}
fg<<nr_comp_conex<<"\n";
for(int i= 0 ; i<nr_comp_conex ; i++){
for(auto j= componente[i].begin(); j!=componente[i].end(); j++)
fg<<*j + 1<<" ";
fg<<"\n";
}
/*std::cout<<"\n";
for(int i=0 ; i<n ; i++)
std::cout<<viz[i]<<" ";
std::cout<<"\n";
for(int i=0 ; i<n ; i++)
std::cout<<low[i]<<" ";*/
}
int main() {
f>>n>>m;
graf g(n, m);
for(int i=0 ; i<m ; i++){
f>>a>>b;
g.new_lista(a-1,b-1);
}
g.comp_conex();
return 0;
}