Pagini recente » Cod sursa (job #15340) | Diferente pentru utilizator/playlikeneverb4 intre reviziile 21 si 20 | Diferente pentru utilizator/popoiu.george intre reviziile 32 si 64 | Monitorul de evaluare | Cod sursa (job #260069)
Cod sursa(job #260069)
#include<fstream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define MAXN 100001
struct muchie{int e1, e2;};
int n, m;
vector<int> G[MAXN];
vector< vector<int> > bic;
int desc[MAXN],mlevel[MAXN];
stack<muchie> stiva;
muchie muc;
void afis(int x, int y){
vector<int> linie;
muchie mi;
do{
mi=stiva.top();
stiva.pop();
linie.push_back(mi.e1);
linie.push_back(mi.e2);
}while(mi.e1!=x||mi.e2!=y);
sort(linie.begin(), linie.end());
linie.erase(unique(linie.begin(), linie.end()), linie.end());
bic.push_back(linie);
}
void df(int nod,int tnod, int nivel){
vector<int>::iterator it;
desc[nod]=mlevel[nod]=nivel;
for(it=G[nod].begin();it!=G[nod].end();++it){
if(!desc[*it]){
muc.e1=nod;muc.e2=*it;
stiva.push(muc);
df(*it, nod, nivel+1);
if(mlevel[*it]<mlevel[nod])
mlevel[nod]=mlevel[*it];
if(mlevel[*it]>=nivel) afis(nod, *it);
}
else{
if(*it!=tnod&&desc[*it]<mlevel[nod])
mlevel[nod]=desc[*it];
}
}
}
int main(){
int nrcmp;
int i, x, y;
vector<int>::iterator it;
ifstream f("biconex.in");
f>>n>>m;
for(i=0;i<m;i++){
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
f.close();
df(1,0,1);
nrcmp=bic.size();
ofstream g("biconex.out");
g<<nrcmp<<'\n';
for(i=0;i<nrcmp;i++){
for(it=bic[i].begin();it!=bic[i].end();++it)
g<<*it<<' ';
g<<'\n';
}
g.close();
return 0;
}