Pagini recente » Cod sursa (job #1990578) | Cod sursa (job #1537217) | Cod sursa (job #1422650) | Cod sursa (job #482020) | Cod sursa (job #2792413)
#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::map<int, 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 sortare_lista();
void dfs(int nod);
void comp_conex();
};
graf::graf(int n, int m) {
this->n = n;
this->m = m;
}
void graf::new_lista(int nod1, int nod2){
lista[nod1].push_back(nod2);
//lista[nod2].push_back(nod1);
}
void graf::dfs(int nod){
int nr_copii = 0;
static int cnt = 0;
viz[nod] = ++cnt;
low[nod] = cnt;
st.push_back(nod);
membru[nod] = 1;
//std::cout<<nod<<" ";
for( auto i = lista[nod].begin(); i != lista[nod].end(); i++){
//std::cout<<"Nodul: "<<nod<<"\n";
//std::cout<<"vecinul: "<<*i<<"\n";
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]){
while(st.back() != nod){
aux = st.back();
//std::cout<< aux<<" ";
std::vector<int>v;
componente.push_back(v);
componente[nr_comp_conex].push_back(aux);
membru[aux] = 0;
st.pop_back();
}
aux = st.back();
//std::cout<< aux<<" ";
componente[nr_comp_conex].push_back(aux);
membru[aux] = 0;
st.pop_back();
++nr_comp_conex;
}
}
}
void graf::comp_conex(){
for(auto i = 0 ; i<=n ; i++){
viz.push_back(-1);
low.push_back(-1);
membru.push_back(0);
}
for(int i = 0 ; i< n ; i++){
if(viz[i] == -1) dfs(i);
}
fg<<nr_comp_conex<<"\n";
for(auto i= 0 ; i<nr_comp_conex ; i++){
for(auto j=0; j<componente[i].size(); j++)
fg<<componente[i][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,b);
}
g.comp_conex();
return 0;
}