Pagini recente » Cod sursa (job #2503359) | Cod sursa (job #2494830) | Cod sursa (job #2519617) | Cod sursa (job #2884163) | Cod sursa (job #2873045)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int N=1e5;
struct graf
{
vector<int> v;
} la[N+5];
int id,muchiiAfara,nrBiconex=0;
int ids[N+5],low[N+5];
bool punctArt[N+5];
void dfs(int rad,int nod,int tata)
{
if(rad == tata) muchiiAfara++;
ids[nod]=low[nod]=++id;
for(int i=0; i<la[nod].v.size(); i++)
{
int to=la[nod].v[i];
if(!ids[to])
{
dfs(rad,to,nod);
low[nod]=min(low[nod],low[to]);
if(ids[nod] <= low[to]) punctArt[nod]=1;
}
else low[nod]=min(low[nod],ids[to]);
}
}
void detPuncteArt(int n)
{
for(int i=1; i<=n; i++)
{
if(!ids[i])
{
muchiiAfara=0;
dfs(i,i,-1);
if(muchiiAfara>1) punctArt[i]=1;
}
}
for(int i=1;i<=n;i++)
if(punctArt[i]) nrBiconex++;
}
int main()
{
int n,m;
in>>n>>m;
for(int i=1; i<=m; i++)
{
int x,y;
in>>x>>y;
la[x].v.push_back(y);
la[y].v.push_back(x);
}
detPuncteArt(n);
cout<<nrBiconex<<'\n';
return 0;
for(int i=1;i<=n;i++)
{
if(punctArt[i] && low[i]!=i) cout<<low[i]<<' '<<i<<'\n';
else
{
cout<<low[i]<<' ';
if(low[i] == i) i++;
while(!punctArt[i] && i<=n)
{
cout<<i<<' ';
i++;
}
if(i<=n)cout<<i<<'\n';
i--;
}
}
for(int i=1; i<=n; i++)
cout<<low[i]<<' ';
cout<<'\n';
for(int i=1; i<=n; i++)
cout<<punctArt[i]<<' ';
return 0;
}