tanasaradu

Untitled

Oct 22nd, 2017
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream fin("ctc.in");
  4. ofstream fout("ctc.out");
  5. const int NMAX=100005;
  6. int n,m,tmp[NMAX],k,nrcmp;
  7. vector<int>L[NMAX];
  8. vector<int>Q[NMAX];
  9. vector<int>SOL[NMAX];
  10. bitset<NMAX>viz;
  11. inline void READ()
  12. {
  13. int nd,nd1;
  14. fin>>n>>m;
  15. while(m--)
  16. {
  17. fin>>nd>>nd1;
  18. L[nd].push_back(nd1);
  19. Q[nd1].push_back(nd);
  20. }
  21. }
  22. void DFS_FIRST(int varf)
  23. {
  24. viz[varf]=1;
  25. for(auto i:L[varf])
  26. if(!viz[i])
  27. DFS_FIRST(i);
  28. ++k;
  29. tmp[k]=varf;
  30. }
  31. void DFS_SECOND(int varf)
  32. {
  33. viz[varf]=1;
  34. for(auto i:Q[varf])
  35. if(!viz[i])
  36. DFS_SECOND(i);
  37. SOL[nrcmp].push_back(varf);
  38. }
  39. inline void SOLVE()
  40. {
  41. for(int i=1;i<=n;i++)
  42. if(!viz[i])
  43. DFS_FIRST(i);
  44. viz.reset();
  45. for(int i=k;i>=1;i--)
  46. {
  47. int j=tmp[i];
  48. if(!viz[j])
  49. {
  50. nrcmp++;
  51. DFS_SECOND(j);
  52. }
  53. }
  54. fout<<nrcmp<<"\n";
  55. for(int i=1;i<=nrcmp;i++)
  56. {
  57. int lug=SOL[i].size();
  58. for(int j=0;j<lug;j++)
  59. fout<<SOL[i][j]<<" ";
  60. fout<<"\n";
  61. }
  62.  
  63. }
  64. int main()
  65. {
  66. READ();
  67. SOLVE();
  68. fin.close();
  69. fout.close();
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment