Pagini recente » Cod sursa (job #89974) | Cod sursa (job #1523366) | Cod sursa (job #1512418) | Cod sursa (job #2095268) | Cod sursa (job #3296220)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
typedef vector <int> vint;
const int nmax = 100000;
int n, m, a, b, clan[nmax + 2];
vint nextt[nmax + 2], chain[nmax + 2];
vint reversegraph[nmax + 2];
int postordine[nmax + 2], countt, tareconex;
int flagg;
void dfsnorm(int node){
clan[node] = 1;
for(auto nxt : nextt[node])
if(!clan[nxt]) dfsnorm(nxt);
postordine[++countt] = node;
return;
}
void dfsinv(int node){
clan[node] = 0; ///out<<node<<" ";
chain[tareconex].push_back(node);
for(auto nxt : reversegraph[node])
if(clan[nxt]) dfsinv(nxt);
return;
}
int main(){
in>>n>>m;
for(int i = 1; i <= m; i++){
in>>a>>b;
nextt[a].push_back(b);
reversegraph[b].push_back(a);
}
countt = 0;
for(int i = 1; i <= n; i++){
if(!clan[i]){
dfsnorm(i);
}
}
///countt = 0;
for(int i = n; i >= 1; i--){
if(clan[postordine[i]]){
tareconex++;
dfsinv(postordine[i]);
}
}
out<<tareconex<<"\n";
for(int i = 1; i <= tareconex; i++){
for(auto it : chain[i])
out<<it<<" ";
out<<"\n";
}
return 0;
}