Pagini recente » Cod sursa (job #1405045) | Cod sursa (job #2373464) | Cod sursa (job #3005583) | Cod sursa (job #2400951) | Cod sursa (job #1165809)
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100000
using namespace std;
vector<vector<int> > graf,cc;
vector<int> isVisited,temp;
vector<pair<int,int> >nodes;
int n,m,k,nn[nmax+1],low[nmax+1];
int minmin(int a,int b)
{
if(a<=b)return a;
return b;
}
void getcc()
{
//needs to be changes
temp.push_back(nodes[0].first);
for(int i=0;i<nodes.size();i++)
temp.push_back(nodes[i].second);
cc.push_back(temp);
temp.clear();
nodes.clear();
}
void DFS(int CN,int nivel)
{
unsigned i;
nn[CN]=low[CN]=nivel;
for(i=0;i<graf[CN].size();i++)
{
if(graf[CN][i]==CN)continue;
if(nn[graf[CN][i]]==0)
{
DFS(graf[CN][i],nivel+1);
nodes.push_back(make_pair(CN, graf[CN][i]));
low[CN]= minmin(low[CN],low[graf[CN][i]]);
if(low[graf[CN][i]]>=nn[CN])
getcc();
}
else
{
low[CN]= minmin(low[CN],nn[graf[CN][i]]);
}
}
}
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
int i,u,v;
f>>n>>m;
graf.resize(n+1);
isVisited.resize(n+1);
for(i=1;i<=m;i++)
{
f>>u>>v;
graf[u].push_back(v);
graf[v].push_back(u);
}
DFS(1,1);
g<<cc.size()<<'\n';
/*
for(i=0;i<cc.size();++i)
{
for(int j=0;j<cc[i].size();j++)
cout<<cc[i][j]<<' ';
cout<<'\n';
}
*/
return 0;
}