Pagini recente » Cod sursa (job #2165909) | Cod sursa (job #318316) | Cod sursa (job #948334) | Cod sursa (job #867499) | Cod sursa (job #567133)
Cod sursa(job #567133)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> a[100001];
vector< pair<int,int> > s;
vector< pair<int,int> > breakpoint;
int n,m,step=0,fii=0,nrcomp;
vector<int> dfn(100001,-1);
vector<int> low(100001,-1);
void readData(){
int i,x,y;
freopen("biconex.in","r",stdin);
scanf("%d %d",&n,&m);
for(i=0;i<m;++i){
scanf("%d %d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
}
void biconex(int x,int tx){
int i,y;
dfn[x]=low[x]=++step;
for(i=0;i<a[x].size();++i){
y=a[x][i];
if(y!=tx && dfn[y]<dfn[x])
s.push_back(make_pair(x,y));
if(dfn[y]==-1){
if(x==1)
fii++;
biconex(y,x);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
// printf("%d %d,",x,y);
breakpoint.push_back(make_pair(x,y));
nrcomp++;
}
}
else if(y!=tx)
low[x]=min(low[x],dfn[y]);
}
}
void afisare(int st, int fin){
vector< pair<int,int> >::iterator it;
sort(s.begin()+st,s.begin()+fin+1);
for(it=s.begin()+st;it<=s.begin()+fin;++it)
printf("(%d %d),",it->first,it->second);
}
int main(){
readData();
freopen("biconex.out","w",stdout);
biconex(1,-1);
printf("%d\n",nrcomp);
return 0;
}