Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin("ctc.in");
- ofstream fout("ctc.out");
- const int NMAX=100005;
- int n,m,tmp[NMAX],k,nrcmp;
- vector<int>L[NMAX];
- vector<int>Q[NMAX];
- vector<int>SOL[NMAX];
- bitset<NMAX>viz;
- inline void READ()
- {
- int nd,nd1;
- fin>>n>>m;
- while(m--)
- {
- fin>>nd>>nd1;
- L[nd].push_back(nd1);
- Q[nd1].push_back(nd);
- }
- }
- void DFS_FIRST(int varf)
- {
- viz[varf]=1;
- for(auto i:L[varf])
- if(!viz[i])
- DFS_FIRST(i);
- ++k;
- tmp[k]=varf;
- }
- void DFS_SECOND(int varf)
- {
- viz[varf]=1;
- for(auto i:Q[varf])
- if(!viz[i])
- DFS_SECOND(i);
- SOL[nrcmp].push_back(varf);
- }
- inline void SOLVE()
- {
- for(int i=1;i<=n;i++)
- if(!viz[i])
- DFS_FIRST(i);
- viz.reset();
- for(int i=k;i>=1;i--)
- {
- int j=tmp[i];
- if(!viz[j])
- {
- nrcmp++;
- DFS_SECOND(j);
- }
- }
- fout<<nrcmp<<"\n";
- for(int i=1;i<=nrcmp;i++)
- {
- int lug=SOL[i].size();
- for(int j=0;j<lug;j++)
- fout<<SOL[i][j]<<" ";
- fout<<"\n";
- }
- }
- int main()
- {
- READ();
- SOLVE();
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment