Pagini recente » Cod sursa (job #2008105) | Cod sursa (job #1961694) | Cod sursa (job #2180956) | Cod sursa (job #437549) | Cod sursa (job #2083764)
#include <bits/stdc++.h>
using namespace std;
int n, m, dfn[100005], low[100005], p, sol;
vector<int> v[100005];
bool ok[100005];
void df(int x, int tata)
{
ok[x] = 1;
low[x] = dfn[x] = ++p;
int mx = -1;
for (vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it)
if(!ok[*it]){
df(*it, x);
low[x] = min(low[x], low[*it]);
mx = max(mx, low[*it]);
}else if(*it != tata){
low[x] = min(low[x], dfn[*it]);
}
if(mx >= dfn[x]){
//cout << x << "\n";
++sol;
}
}
int main()
{
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
fin >> n >> m;
while(m--){
int x, y;
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 1; i <= n; ++i)
if(!ok[i]){
int nrfii = 0;
dfn[i] = low[i] = ++p;
ok[i] = 1;
++sol;
for (vector<int>::iterator it = v[i].begin(); it != v[i].end(); ++it)
if(!ok[*it]){
++nrfii;
df(*it, i);
}
if(nrfii > 1){
//cout << i << "\n";
++sol;
}
}
fout << sol << "\n";
fin.close();
fout.close();
return 0;
}