unlucky_13

uva_925

Jun 22nd, 2013
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 KB | None | 0 0
  1. /*
  2.  Author                             :     unlucky_13
  3.  Probs_link                         :
  4.  Category                           :
  5.  Algorithm_Used                     :
  6.  */
  7.  
  8. #include<cstdio>
  9. #include<sstream>
  10. #include<cstdlib>
  11. #include<cctype>
  12. #include<cmath>
  13. #include<algorithm>
  14. #include<set>
  15. #include<queue>
  16. #include<stack>
  17. #include<list>
  18. #include<iostream>
  19. #include<fstream>
  20. #include<numeric>
  21. #include<string>
  22. #include<vector>
  23. #include<cstring>
  24. #include<map>
  25. #include<iterator>
  26. #define LL long long int
  27. const long long int inf = 2147483647;
  28. const int min=0;
  29. const int maxn=200;
  30. using namespace std;
  31. int n,m;
  32. map<string,int>G ;
  33. map<string,int>::iterator it,IT;
  34. int gra[maxn][maxn] ;
  35. int deg[maxn],dis[maxn];
  36. int check(int u){
  37.     int ret = 0 ;
  38.     for(int i=0;i<n;i++){
  39.         if(dis[i]==-1) ret++ ;
  40.     }
  41.  
  42.     return ret ;
  43.  
  44. }
  45. void dfs(int u,int par){
  46.     //cout<<GG[u]<<endl ;
  47.     if(dis[u]==1) return ;
  48.     else if(dis[u]==-1){
  49.         dis[u] = 1 ;
  50.         return ;
  51.     }
  52.  
  53.     dis[u]=par ;
  54.  
  55.     for(int i=0;i<deg[u];i++){
  56.                 dfs(gra[u][i],1) ;
  57.     }
  58.  
  59.  
  60. }
  61.  
  62. void topsort(){
  63.  
  64.     for(it=G.begin();it!=G.end();it++){
  65.         memset(dis,0,sizeof(dis)) ;
  66.         int i = it->second ;
  67.         for(int j=0;j<deg[i];j++){
  68.             dfs(gra[i][j],-1) ;
  69.         }
  70.         int flag = check(i) ;
  71.         if(flag){
  72.             cout<<it->first<<" "<<flag;
  73.             for(IT=G.begin();IT!=G.end();IT++){
  74.                 if(dis[IT->second]==-1) cout<<" "<<IT->first;
  75.             }
  76.  
  77.             cout<<endl ;
  78.         }
  79.     }
  80.  
  81. }
  82.  
  83. int main() {
  84.  
  85.     freopen("C:\\Users\\Mazhar\\Desktop\\in.txt", "r", stdin);
  86.     int tc ;
  87.     string s ;
  88.     scanf("%d",&tc) ;
  89.     while(tc--){
  90.         G.clear() ;
  91.         scanf("%d\n",&n) ;
  92.         for(int i=0;i<n;i++){
  93.             cin>>s ;
  94.             G[s]=i ;
  95.             deg[i]=0 ; //was geting WA for this
  96.         }
  97.  
  98.         scanf("%d\n",&m) ;
  99.         while(m--){
  100.             cin>>s;
  101.             int u = G[s] ;
  102.             cin>>deg[u] ;
  103.             for(int i=0;i<deg[u];i++){
  104.                 cin>>s ;
  105.                 gra[u][i] = G[s] ;
  106.             }
  107.  
  108.         }
  109.  
  110.  
  111.         topsort() ;
  112.  
  113.     }
  114.  
  115.  
  116.     return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment