Pagini recente » Cod sursa (job #1425174) | Cod sursa (job #2544245) | Cod sursa (job #1793593) | Cod sursa (job #2523607) | Cod sursa (job #3216008)
#include <iostream>
#include <vector>
#define MAXN 100010
using namespace std;
struct node{
int lvl, currLvl, t;
vector <int> neighbours;
};
node graph[MAXN];
vector <int> ans[MAXN];
int ansSize;
int t;
int dfsId;
vector <int> aux;
void dfs(int pos) {
graph[pos].currLvl = graph[pos].lvl = t;
graph[pos].t = dfsId;
aux.push_back(pos);
t++;
for ( int v : graph[pos].neighbours ) {
if ( graph[v].t == 0 || graph[v].t == dfsId ) {
if ( graph[v].t == 0 ) {
dfs(v);
}
graph[pos].lvl = min(graph[pos].lvl, graph[v].lvl);
}
}
if ( graph[pos].currLvl == graph[pos].lvl ) {
while ( aux.back() != pos ) {
ans[ansSize].push_back(aux.back());
aux.pop_back();
}
ans[ansSize].push_back(pos);
ansSize++;
aux.pop_back();
}
}
void addEdge(int a, int b) {
graph[a].neighbours.push_back(b);
}
int main() {
FILE *fin, *fout;
fin = fopen("ctc.in", "r");
fout = fopen("ctc.out", "w");
int n, m, i, a, b;
fscanf(fin, "%d%d", &n, &m);
for ( i = 0; i < m; i++ ) {
fscanf(fin, "%d%d", &a, &b);
addEdge(a, b);
}
dfsId = 1;
ansSize = 0;
for ( i = 1; i <= n; i++ ) {
if ( !graph[i].t ) {
dfs(i);
dfsId++;
}
}
fprintf(fout, "%d\n", ansSize);
for ( i = 0; i < ansSize; i++ ) {
for ( int v : ans[i] ) {
fprintf(fout, "%d ", v);
}
fprintf(fout, "\n");
}
fclose(fin);
fclose(fout);
return 0;
}