Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Author : unlucky_13
- Probs_link :
- Category :
- Algorithm_Used :
- */
- #include<cstdio>
- #include<sstream>
- #include<cstdlib>
- #include<cctype>
- #include<cmath>
- #include<algorithm>
- #include<set>
- #include<queue>
- #include<stack>
- #include<list>
- #include<iostream>
- #include<fstream>
- #include<numeric>
- #include<string>
- #include<vector>
- #include<cstring>
- #include<map>
- #include<iterator>
- #define LL long long int
- const long long int inf = 2147483647;
- const int min=0;
- const int maxn=200;
- using namespace std;
- int n,m;
- map<string,int>G ;
- map<string,int>::iterator it,IT;
- int gra[maxn][maxn] ;
- int deg[maxn],dis[maxn];
- int check(int u){
- int ret = 0 ;
- for(int i=0;i<n;i++){
- if(dis[i]==-1) ret++ ;
- }
- return ret ;
- }
- void dfs(int u,int par){
- //cout<<GG[u]<<endl ;
- if(dis[u]==1) return ;
- else if(dis[u]==-1){
- dis[u] = 1 ;
- return ;
- }
- dis[u]=par ;
- for(int i=0;i<deg[u];i++){
- dfs(gra[u][i],1) ;
- }
- }
- void topsort(){
- for(it=G.begin();it!=G.end();it++){
- memset(dis,0,sizeof(dis)) ;
- int i = it->second ;
- for(int j=0;j<deg[i];j++){
- dfs(gra[i][j],-1) ;
- }
- int flag = check(i) ;
- if(flag){
- cout<<it->first<<" "<<flag;
- for(IT=G.begin();IT!=G.end();IT++){
- if(dis[IT->second]==-1) cout<<" "<<IT->first;
- }
- cout<<endl ;
- }
- }
- }
- int main() {
- freopen("C:\\Users\\Mazhar\\Desktop\\in.txt", "r", stdin);
- int tc ;
- string s ;
- scanf("%d",&tc) ;
- while(tc--){
- G.clear() ;
- scanf("%d\n",&n) ;
- for(int i=0;i<n;i++){
- cin>>s ;
- G[s]=i ;
- deg[i]=0 ; //was geting WA for this
- }
- scanf("%d\n",&m) ;
- while(m--){
- cin>>s;
- int u = G[s] ;
- cin>>deg[u] ;
- for(int i=0;i<deg[u];i++){
- cin>>s ;
- gra[u][i] = G[s] ;
- }
- }
- topsort() ;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment