Pagini recente » Cod sursa (job #1411118) | Cod sursa (job #1960219) | Cod sursa (job #2326054) | Cod sursa (job #2123002) | Cod sursa (job #1832704)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
int n, m, nivelActual[100005], nivelSus[100005], viz[100005], numarComponente=0;
vector <int> g[100005];
vector <vector <int> > vect;
stack <int> s;
void read()
{
scanf("%d%d", &n, &m);
int x, y;
for(int i=1; i<=m; ++i)
{
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
}
void adaugareComponente(int x, int nod)
{
vector <int>::iterator it;
vector <int> aux;
aux.push_back(nod);
while(s.top()!=x)
{
aux.push_back(s.top());
s.pop();
}
aux.push_back(x);
s.pop();
vect.push_back(aux);
}
void dfs(int x, int tata)
{
vector <int>::iterator it;
viz[x]=1;
nivelActual[x]=nivelActual[tata]+1;
nivelSus[x]=nivelActual[x];
for(it=g[x].begin(); it!=g[x].end(); ++it)
{
if(*it==tata)
continue;
if(viz[*it]==0)
{
s.push(*it);
dfs(*it, x);
if(nivelSus[*it]<nivelSus[x])
nivelSus[x]=nivelSus[*it];
if(nivelSus[*it]>=nivelActual[x])
{
numarComponente++;
//adaugareComponente(*it, x);
}
}
else
{
if(nivelSus[*it]<nivelSus[x])
nivelSus[x]=nivelSus[*it];
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
read();
nivelActual[0]=-1;
for(int i=1; i<=n; ++i)
{
s.push(i);
if(viz[i]==0)
dfs(i, 0);
s.pop();
}
printf("%d\n", numarComponente);
/*vector <vector <int> >::iterator itvect;
vector <int>::iterator it;
for(itvect=vect.begin(); itvect!=vect.end(); ++itvect)
{
for(it=itvect->begin(); it!=itvect->end(); ++it)
printf("%d ", *it);
printf("\n");
}*/
return 0;
}