Pagini recente » Cod sursa (job #1855851) | Cod sursa (job #1837608) | Cod sursa (job #2401476) | Cod sursa (job #182580) | Cod sursa (job #1143383)
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
FILE *f,*g;
const int N=100001;
vector< pair<int, int> > muchii;
vector<int> veci[N],varfuri,unic;
vector< vector<int> > comp;
stack< pair<int, int> > alledge;
int depth[100001],updepth[100001],n,m,nr;
bool seen[100001];
void makecomp(void){
nr++;
varfuri.clear();
unic.clear();
vector< pair<int,int > >::iterator edge;
edge=muchii.begin();
while(edge!=muchii.end()){
varfuri.push_back(edge->first);
varfuri.push_back(edge->second);
edge++;
}
sort(varfuri.begin(),varfuri.end());
comp.push_back(varfuri);
vector<int>::iterator varf;
varf=varfuri.begin();
int curr=*varf;
unic.push_back(curr);
while(varf!=varfuri.end()){
if (*varf!=curr){
curr=*varf;
unic.push_back(curr);
}
varf++;
}
comp.push_back(unic);
}
void dfs(int n){
updepth[n]=depth[n];
seen[n]=1;
vector<int>::iterator it=veci[n].begin();
while(it!=veci[n].end()){
if (!seen[*it]){
alledge.push(make_pair(n,*it));
depth[*it]=depth[n]+1;
printf("good%d",n);
dfs(*it);
updepth[n]=min(updepth[n],updepth[*it]);
if (updepth[*it]>=depth[n]){
muchii.clear();
while (alledge.top()!=make_pair(n,*it)) {
muchii.push_back(alledge.top());
alledge.pop();
}
muchii.push_back(alledge.top());
alledge.pop();
makecomp();
}
}
else if (depth[*it]<updepth[n]) updepth[n]=depth[*it];
printf("good%d",n);
it++;
}
}
void read(void){
f=fopen("biconex.in","r");
g=fopen("biconex.out","w");
fscanf(f,"%d%d",&n,&m);
int i,a,b;
for(i=1;i<=m;i++){
fscanf(f,"%d%d",&a,&b);
veci[a].push_back(b);
veci[b].push_back(a);
}
}
int main(void){
read();
dfs(1);
vector< vector< int > >::iterator it;
vector<int>::iterator ti;
it=comp.begin();
fprintf(g,"%d\n",nr);
while(it!=comp.end()){
ti=(*it).begin();
while(ti!=(*it).end()) {
fprintf(g,"%d ",*ti);
ti++;
}
fprintf(g,"\n");
it++;
}
return 0;
}