Pagini recente » Cod sursa (job #2171268) | Cod sursa (job #376316) | Cod sursa (job #1538521) | Cod sursa (job #818550) | Cod sursa (job #590583)
Cod sursa(job #590583)
#include <fstream>
#define max_n 100001
#define max_m 200001
using namespace std;
typedef struct point {
int inf;
point *leg;
};
point *g[max_n];
int u[max_n],t[max_n],l[max_n],st[max_m][2],nv[max_n];
int i,j,n,m,nr,x,y,nrc;
ifstream f ("biconex.in");
ofstream f2 ("biconex.out");
void adauga(int i,int j){
point *p;
p=new point;
p->inf=i;
p->leg=g[j];
g[j]=p;
}
void push(int i,int j) {
st[nr][0]=i;
st[nr++][1]=j;
}
void pop (int &i,int &j) {
i=st[--nr][0];
j=st[nr][1];
}
void Df(int nod) {
point *p;
int x,y;
u[nod]=1;
l[nod]=nv[nod];
for (p=g[nod]; p!=NULL; p=p->leg) {
if (p->inf!=t[nod] && nv[nod]>nv[p->inf])
push(p->inf,nod);
if (!u[p->inf]) {
nv[p->inf]=nv[nod]+1;
t[p->inf]=nod;
Df(p->inf);
if (l[nod]>l[p->inf])
l[nod]=l[p->inf];
if (l[p->inf]>=nv[nod]) {
nrc++;
do {
pop(x,y);
//f2 << x <<' ' << y << ' ';
}
while (!(x==nod && y==p->inf) && !(x==p->inf && y==nod));
//f2 << '\n';
}
}
else
if (p->inf!=t[nod] && l[nod]>nv[p->inf])
l[nod]=nv[p->inf];
}
}
int main () {
f >> n >> m;
nr=0;
nrc=0;
for (i=1; i<=m; i++) {
f >> x >> y;
adauga(x,y);
adauga(y,x);
}
for (i=1; i<=n; i++) {
if (!u[i]) {
nv[i]=1;
Df(i);
}
}
f2 << nrc << '\n';
f.close();
f2.close();
return 0;
}