Pagini recente » Cod sursa (job #2678046) | Cod sursa (job #616964) | Cod sursa (job #304718) | Profil MihneaGhira | Cod sursa (job #2437066)
// Matteo Verzotti - C++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <ctime>
#include <map>
#include <chrono>
#include <cmath>
#define INF 0x3f3f3f3f
#define MAX(a,b) a>b ? a:b
#define MIN(a,b) a<b ? a:b
using namespace std;
const int NODE = 1e5;
vector <int> g[NODE+5],gt[NODE+5],ctc[NODE+5];
stack <int> st;
bool viz[NODE+5];
int n, m, x, y, nrctc;
void DFS(int node) {
viz[node] = 1;
for(int i=0; i<g[node].size(); i++) {
int vecin = g[node][i];
if(!viz[vecin])
DFS(vecin);
}
st.push(node);
}
void DFS2(int node) {
viz[node] = 0;
ctc[nrctc].push_back(node);
for(int i=0; i<gt[node].size(); i++) {
int vecin = gt[node][i];
if(viz[vecin])
DFS2(vecin);
}
}
void solve() {
for(int i=1; i<=n; i++)
if(!viz[i])
DFS(i);
while(st.size()) {
int node = st.top();
if(viz[node]){
DFS2(node);
nrctc++;
}
st.pop();
}
}
int main() {
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++) {
scanf("%d%d",&x,&y);
g[x].push_back(y);
gt[y].push_back(x);
}
solve();
printf("%d\n",nrctc);
for(int i=0;i<nrctc;i++){
for(int j=0;j<ctc[i].size();j++)
printf("%d ",ctc[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}