Pagini recente » Cod sursa (job #623986) | Cod sursa (job #675806) | Cod sursa (job #1312299) | Cod sursa (job #3235776) | Cod sursa (job #2926600)
#include <iostream>
#include <vector>
#define MAXN 100000
using namespace std;
struct node{
vector <int> edges;
int smallestLvl;
bool isInStack;
bool visited;
int posInV;
};
node graph[MAXN + 1];
int v[MAXN];
int vSize;
vector <int> ans[MAXN];
int ansSize;
void addEdge(int a, int b) {
graph[a].edges.push_back(b);
}
void dfs(int pos, int lvl) {
int i;
graph[pos].smallestLvl = lvl;
v[vSize] = pos;
vSize++;
graph[pos].isInStack = true;
graph[pos].visited = true;
for ( int i : graph[pos].edges ) {
if ( graph[i].smallestLvl == -1 ) {
dfs(i, lvl + 1);
graph[pos].smallestLvl = min(graph[pos].smallestLvl, graph[i].smallestLvl);
}
if ( graph[i].isInStack ) {
graph[pos].smallestLvl = min(graph[pos].smallestLvl, graph[i].smallestLvl);
}
}
if ( graph[pos].smallestLvl == lvl ) {
do {
vSize--;
ans[ansSize].push_back(v[vSize]);
graph[v[vSize]].isInStack = false;
graph[v[vSize]].smallestLvl = lvl;
} while ( v[vSize] != pos );
ansSize++;
}
}
int main() {
FILE *fin, *fout;
fin = fopen("ctc.in", "r");
fout = fopen("ctc.out", "w");
int n, m, i, a, b, i2;
fscanf(fin, "%d%d", &n, &m);
for ( i = 1; i <= n; i++ ) {
graph[i].smallestLvl = -1;
}
for ( i = 0; i < m; i++ ) {
fscanf(fin, "%d%d", &a, &b);
addEdge(a, b);
}
vSize = ansSize = 0;
for ( i = 1; i <= n; i++ ) {
if ( !graph[i].visited ) {
dfs(i, 0);
}
}
fprintf(fout, "%d\n", ansSize);
for ( i = 0; i < ansSize; i++ ) {
for ( i2 = 0; i2 < ans[i].size(); i2++ ) {
fprintf(fout, "%d ", ans[i][i2]);
}
fprintf(fout, "\n");
}
return 0;
}