JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Uva networks | Reply
I was trying this problem on articulation points after reading about it. But i am getting wrong answer everytime
#include <iostream>
#include <cstdio>
#include <sstream>
#include <stack>
#include <vector>
#include <map>
#include <ctype.h>
#include <set>
#include <climits>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define sz size()
#define pb push_back
#define _(x,a) memset(x,a,sizeof(x))
#define LET(x,a) typeof(a) x(a)
#define FOR(i,a,b) for(LET(i,a);i!=(b);++i)
#define REP(i,n) FOR(i,0,n)
#define EACH(i,v) FOR(i,(v).begin(),(v).end())
#define LL long long
#define M 1000000007
#define f first
#define INF 1<<30
#define sec second
int ct;
vector <int> vis(101);
vector <int> parse(string s)
{
stringstream ss(s);
ss<<s;
int temp;
vector ><int> ret;
while(ss>>temp)
ret.pb(temp);
return ret;
}
vector < vector<int> > g(101);
vector <int> low(101),num(101),parent(101);
int ans;
vector <int> art(101);
void dfs(int u)
{
vis[u]=1;
low[u]=num[u]=ct++;
REP(i,g[u].sz)
{
int w=g[u][i];
if(!vis[w])
{
parent[w]=u;
dfs(w);
if(low[w]>=num[u]&&!art[u]){art[u]=1;ans++;}
low[u]=min(low[w],low[u]);
}
else
{
if(parent[u]!=w)
low[u]=min(low[u],num[w]);
}
}
}
int main()
{
int n;
cin>>n;
while(n!=0)
{
REP(i,n){g[i].clear();low[i]=-1;num[i]=-1;vis[i]=0;parent[i]=0;art[i]=0;}
string s;
getline(cin,s);
while(getline(cin,s))
{
//cout<<<endl;
stringstream ss(s);
ss<<s;
int temp;
vector ><int> v(101);
int k=0;
while(ss>>temp){v[k++]=temp;}
//REP(i,k)cout<<v[i]><<" ";cout<<endl;
if(v[0]==0&&k==1)break;
int u=v[0];
FOR(i,1,k)
{
g[u-1].pb(v[i]-1);g[v[i]-1].pb(u-1);
}
}
//REP(i,n){REP(j,g[i].sz)cout><<g[i][j]<<" ";cout<<endl;}
ans=0,ct=0;
REP(i,n)
{
if(!vis[i])
dfs(i);
}
if(g[0].sz>1)
cout<<ans><<endl;
else cout<<ans-1><<endl;
cin>>n;
}
return 0;
}
thnx in advance
RSS