Pagini recente » Cod sursa (job #611360) | Cod sursa (job #2831282) | Cod sursa (job #2757217) | Cod sursa (job #2233008) | Cod sursa (job #930106)
Cod sursa(job #930106)
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <deque>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
#define nmax 100005
int n, m, Min[nmax], nivel[nmax], t[nmax];
bool viz[nmax];
deque< pair<int,int> > dq;
vector<int> Comp[nmax], gf[nmax];
int comp = 0;
void citeste(){
f >> n >> m;
int x, y;
for(int i=1; i<=m; ++i){
f >> x >> y;
gf[x].push_back(y);
gf[y].push_back(x);
}
}
void bagaComp(int nod, int vc){
++comp; // apare o noua componenta
int X = dq.back().first; int Y = dq.back().second;
dq.pop_back();
while( (X != nod || Y != vc) && ( X != vc || Y != nod ) ){
Comp[comp].push_back(X); Comp[comp].push_back(Y);
X = dq.back().first; Y = dq.back().second;
dq.pop_back();
}
Comp[comp].push_back(X); Comp[comp].push_back(Y);
}
void dfs(int nod){
viz[nod] = 1;
for(int i=0; i<gf[nod].size(); ++i){
int vc = gf[nod][i];
if (viz[vc] == 0){
t[vc] = nod;
nivel[vc] = nivel[nod] + 1;
Min[vc] = nivel[vc];// initial
dq.push_back( make_pair(nod, vc) );
dfs(vc);
Min[nod] = min(Min[nod], Min[vc]);
if (Min[vc] >= nivel[nod]){// => pot ajune pana in nod maxim daca il scot
// pe nod nu o sa mai pot ajunge in vc
bagaComp(nod, vc);
}
}else if (t[vc] != nod){// ma duc din nod in vc (asta fiind o muchie de intoarcere)
Min[nod] = min(Min[nod], nivel[vc]);// am voie sa ma duc pe maxim o muchie de intoarcere
}
}
}
void rezolva(){
for(int i=1; i<=n; ++i){
if (viz[i] == 0)
dfs(i);
}
g << comp << "\n";
for(int i=1; i<=comp; ++i){
sort(Comp[i].begin(), Comp[i].end() );
for(int j=1; j<Comp[i].size(); ++j){
if (Comp[i][j] != Comp[i][j-1]){
g << Comp[i][j-1] << " ";
}
}
g << Comp[i][ Comp[i].size()-1 ] << "\n";
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}