Pagini recente » Cod sursa (job #2152860) | Cod sursa (job #381502) | Cod sursa (job #1128580) | Cod sursa (job #2485688) | Cod sursa (job #3296212)
#include <fstream>
#include <queue>
#include <vector>
///#pragma GCC optimize("O3", "unroll-loops")
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];
vint chain[nmax + 2];
vint reversegraph[nmax + 2];
int postordine[nmax + 2], countt, tareconex;
/**void bfs(int node){
queue <int> dq;
dq.push(node);
clan[node] = node;
for(int noww; !dq.empty(); ){
noww = dq.front();
out<<noww<<" "; dq.pop();
for(auto nxt : nextt[noww]){
if(!clan[nxt]){
clan[nxt] = node;
dq.push(nxt);
}
}
}
out<<"\n";
return;
}**/
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[flagg].push_back(node);
for(auto nxt : reversegraph[node])
if(clan[nxt]) dfsinv(nxt);
///postordine[++countt] = node;
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]){
flagg = i;
dfsnorm(i);
}
}
countt = 0;
for(int i = n; i >= 1; i--){
if(clan[i]){
flagg = i;
dfsinv(i);
tareconex++;
}
}
out<<tareconex<<"\n";
for(int i = 1; i <= n; i++){
for(auto it : chain[i])
out<<it<<" ";
if(!chain[i].empty()) out<<"\n";
}
return 0;
}