Skip to content

Instantly share code, notes, and snippets.

@harshraj22
Created June 30, 2019 07:52
Show Gist options
  • Save harshraj22/10d1237f8a1395f61fe66f23a8156586 to your computer and use it in GitHub Desktop.
Save harshraj22/10d1237f8a1395f61fe66f23a8156586 to your computer and use it in GitHub Desktop.
Getting weired error in ques 10199 of uva online judge.
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int N=104;
vector<int> g[N],lt,in,ap,vis;
int tim=0;
#define eb emplace_back
void dfs(int node,int par=-1){
vis[node]=1;
lt[node]=in[node]=tim++;
int child=0;
for(auto it:g[node]){
if(it==par)continue;
else if(vis[it]==1)
lt[node]=min(lt[node],lt[it]);
else{
dfs(it,node);
lt[node]=min(lt[node],lt[it]);
if(lt[it]>=in[node] && par!=-1)
ap.eb(node);
child++;
}
}
if(par==-1 && child>1)ap.eb(node);
}
int calc(int n){
for(int i=1;i<=n;i++){
tim=0;
if(vis[i]==0)
dfs(i);
}
return ap.size();
}
int main(){
ios_base::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
int n=1; cin>>n;
while(1){
for(auto &it:g)it.clear();
lt.resize(n,0); in.resize(n,0); ap.clear(); vis.resize(n,0);
map<string,int> lk;
int i,j,k,m;
for(i=1;i<=n;i++){
string s;
cin>>s; lk[s]=i;
}
cin>>m;
while(m--){
string s,ss;
cin>>s>>ss;
g[lk[s]].eb(lk[ss]);
g[lk[ss]].eb(lk[s]);
}
// cout<<"part 1 : \n";
cout<<calc(n)<<"\n";
cin>>n;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment