Pagini recente » Cod sursa (job #2664626) | Cod sursa (job #29392) | Cod sursa (job #2210715) | Cod sursa (job #1160787) | Cod sursa (job #2793519)
#include <bits/stdc++.h>
#include<fstream>
#include<vector>
#include<map>
#include<queue>
#include<deque>
std::ifstream f("biconex.in");
std::ofstream fg("biconex.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<std::set<int>> componente;
std::vector<int> viz;
std::vector<int> low;
std::vector<int> tata;
std::deque<int> st;
std::deque<std::pair<int, int>> perechi;
int nr_comp_biconex = 0;
void new_lista( int nod1, int nod2);
void dfs(int nod);
void biconex();
};
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);
tata.push_back(-1);
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;
std::set<int> s;
viz[nod] = ++cnt;
low[nod] = cnt;
st.push_back(nod);
int nr_copii = 0;
for( auto i = lista[nod].begin(); i != lista[nod].end(); i++) {
if (viz[*i] == -1) {
tata[*i] = nod;
nr_copii++;
perechi.push_back(std::make_pair(nod, *i));
dfs(*i);
low[nod] = fmin(low[nod], low[*i]);
// std::cout <<nod<<" si "<<*i<< "\n";
// std::cout <<viz[nod]<<" si "<<low[*i]<< "\n";
if ( low[*i] >= viz[nod]) { //e punct de articulatie
componente.push_back(s);
while (perechi.back().first != nod || perechi.back().second != *i) {
componente[nr_comp_biconex].insert(perechi.back().first);
componente[nr_comp_biconex].insert(perechi.back().second);
//std::cout << perechi.back().first << " " << perechi.back().second << " ";
perechi.pop_back();
}
componente[nr_comp_biconex].insert(perechi.back().first);
componente[nr_comp_biconex].insert(perechi.back().second);
//std::cout << perechi.back().first << " " << perechi.back().second << " ";
perechi.pop_back();
++nr_comp_biconex;
//std::cout << "\n";
}
} else if (*i != tata[nod]) {
low[nod] = fmin(low[nod], viz[*i]);
}
}
}
void graf::biconex(){
for(int i = 0 ; i< n ; i++){
if(viz[i] == -1) dfs(i);
}
std::cout<<nr_comp_biconex<<"\n";
for(int i = 0 ; i<nr_comp_biconex ; i++){
for(auto j = componente[i].begin() ; j != componente[i].end() ; j++)
std::cout<< *j + 1<<" ";
std::cout<<"\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.biconex();
return 0;
}