Pagini recente » Cod sursa (job #3167137) | Cod sursa (job #819205) | Cod sursa (job #2929705) | Cod sursa (job #1386188) | Cod sursa (job #1489988)
#include<vector>
#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define MAXN 100005
int n, m, S[MAXN], e, CTC[MAXN], ctc;
vector<int> G[MAXN], Gt[MAXN], Nodes[MAXN];
bool used[MAXN];
void dfsstep1(int node) {
used[node] = 1;
for(auto vec : G[node]) {
if(!used[vec])
dfsstep1(vec);
}
S[++e] = node;
}
void dfsstep2(int node) {
CTC[node] = ctc;
for(auto vec : Gt[node])
if(!CTC[vec])
dfsstep2(vec);
}
int main() {
int a, b, i;
fin>>n>>m;
while(m--) {
fin>>a>>b;
G[a].push_back(b);
Gt[b].push_back(a);
}
for(i=1; i<=n; ++i)
if(!used[i])
dfsstep1(i);
for(i=n; i>=1; i--)
if(!CTC[S[i]])
++ctc, dfsstep2(S[i]);
for(i=1; i<=n; i++)
Nodes[CTC[i]].push_back(i);
fout<<ctc<<'\n';
for(i=1; i<=ctc; ++i){
for(auto comp : Nodes[i])
fout<<comp<<" ";
fout<<'\n';
}
return 0;
}