Pagini recente » Cod sursa (job #3293804) | Cod sursa (job #3293158)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int>g[100001];
vector<int>gt[100001];
vector<int>CTC[100001];
int viz[1000001],ctc;
stack<int>q;
void DFS(int nod) {
viz[nod] = 1;
for (auto x:g[nod])
if(!viz[x])
DFS(x);
q.push(nod);
}
void DFST(int nod) {
viz[nod] = 2;
CTC[ctc].push_back(nod);
for (auto x:gt[nod])
if(viz[x]==1)
DFST(x);
}
int main()
{
int n,m;
cin >> n >> m;
for(int i=0;i<m;i++) {
int x,y;
cin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!viz[i])
DFS(i);
while(!q.empty()) {
int nod = q.top();
if(viz[nod]==1) {
ctc++;
DFST(nod);
}
q.pop();
}
cout << ctc << endl;
for(int i=1;i<=ctc;i++,cout << '\n')
for(int j=0;j<CTC[i].size();j++)
cout << CTC[i][j] << ' ';
return 0;
}