Pagini recente » Cod sursa (job #2095363) | Cod sursa (job #2632273) | Cod sursa (job #1975098) | Cod sursa (job #1139934) | Cod sursa (job #2145750)
#include <bits/stdc++.h>
#define MAXN 100010
std::vector <std::vector<int>> M;
std::vector <int> G[1 + MAXN], BC;
int st[1 + MAXN], inst[1 + MAXN], last, pos[1 + MAXN];
int lowlink[1 + MAXN], seen[1 + MAXN];
int cnt;
void tarjan(int node, int fth){
//st[++last] = node; inst[node] = 1;
pos[node] = lowlink[node] = pos[fth] + 1;
seen[node] = 1;
for(auto y: G[node]){
if(!seen[y]){
tarjan(y, node);
lowlink[node] = std::min(lowlink[node], lowlink[y]);
if(lowlink[y] >= pos[node]){
cnt++;
/*BC.clear();
while(last > pos[node]){
BC.push_back(st[last]);
inst[st[last]] = 0;
last--;
}
BC.push_back(node);
M.push_back(BC);*/
}
}
if(y != fth) lowlink[node] = std::min(lowlink[node], pos[y]);
}
}
int main(){
FILE*fi,*fo;
fi = fopen("biconex.in","r");
fo = fopen("biconex.out","w");
int n, m;
fscanf(fi,"%d%d", &n, &m);
for(int i = 1; i <= m; i++){
int a, b;
fscanf(fi,"%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
tarjan(1, 0);
/*fprintf(fo,"%d\n", M.size());
for(int i = 0; i < M.size(); i++){
for(auto j: M[i]) fprintf(fo,"%d ", j);
fprintf(fo,"\n");
}*/
fprintf(fo,"%d", cnt);
return 0;
}