Pagini recente » Cod sursa (job #1724866) | Cod sursa (job #492867) | Cod sursa (job #2010329) | Cod sursa (job #1333731) | Cod sursa (job #2210933)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define NMAX 100001
stack<int> S;
vector<int> viz;
vector<int> g[NMAX];
vector<int> gt[NMAX];
void dfs(int nod) {
viz[nod] = 1;
for(int i = 0; i < g[nod].size(); i++) {
if(viz[g[nod][i]] == 0) {
dfs(g[nod][i]);
}
}
S.push(nod);
}
void dfsT(int nod, int flag) {
viz[nod] = flag;
for(int i = 0; i < gt[nod].size(); i++) {
if(viz[gt[nod][i]] == 0) {
dfsT(gt[nod][i], flag);
}
}
}
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M;
int a, b;
fin >> N >> M;
for(int i = 0; i < M; i++) {
fin >> a >> b;
g[a].push_back(b);
gt[b].push_back(a);
}
viz.resize(N + 1, 0);
for(int i = 1; i <= N; i++) {
if(viz[i] == 0) {
dfs(i);
}
}
viz.assign(N + 1, 0);
int cnt = 0;
int index = 1;
while(!S.empty()) {
int nod = S.top();
S.pop();
if(viz[nod] == 0) {
dfsT(nod, index);
cnt ++;
index ++;
}
}
vector< vector<int> > sol(cnt + 1);
for(int i = 1; i <= N; i ++) {
sol[viz[i]].push_back(i);
}
fout << cnt << endl;
for(int i = 1; i <= cnt; i ++) {
for(int j = 0; j < sol[i].size(); j ++) {
fout << sol[i][j] << " ";
}
fout << endl;
}
return 0;
}