Pagini recente » Cod sursa (job #2184059) | Cod sursa (job #440928) | Cod sursa (job #252359) | Cod sursa (job #1517521) | Cod sursa (job #1320290)
#include<fstream>
#include<vector>
#include<cstring>
#define MAXN 100001
using namespace std;
typedef int var;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<var> G[MAXN];
vector<var> Gt[MAXN];
vector<var> CC[MAXN];
var n;
var cur_cc;
bool VIZ1[MAXN], VIZ2[MAXN];
vector<int> ST;
void dfs1(var node) {
VIZ1[node] = 1;
for(vector<var>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
if(!VIZ1[*it])
dfs1(*it);
}
ST.push_back(node);
}
void dfs2(var node) {
VIZ2[node] = 1;
CC[cur_cc].push_back(node);
for(vector<var>::iterator it = Gt[node].begin(); it != Gt[node].end(); ++it) {
if(!VIZ2[*it])
dfs2(*it);
}
}
int main() {
var m, a, b;
fin>>n>>m;
while(m--) {
fin>>a>>b;
G[a].push_back(b);
Gt[b].push_back(a);
}
for(var i=1; i<=n; i++) {
if(!VIZ1[i])
dfs1(i);
}
for(var i=n-1; i>=0; i--) {
if(!VIZ2[ST[i]]) {
cur_cc++;
dfs2(ST[i]);
}
}
fout<<cur_cc<<'\n';
for(var i=1; i<=cur_cc; ++i) {
for(vector<var>::iterator it = CC[i].begin(); it!=CC[i].end(); ++it)
fout<<*it<<" ";
fout<<'\n';
}
return 0;
}