Created
June 30, 2019 07:52
-
-
Save harshraj22/10d1237f8a1395f61fe66f23a8156586 to your computer and use it in GitHub Desktop.
Getting weired error in ques 10199 of uva online judge.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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