Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Istoria paginii utilizator/braisa | Istoria paginii utilizator/mihneado | Cod sursa (job #2016937)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000;
vector<int> graph[1+MAX_N];
vector<vector<int> > tare;
int st[MAX_N], top, id[1+MAX_N], low[1+MAX_N];
bool inst[1+MAX_N];
int lastid = 1;
static inline int min(int a, int b) {
if(a < b)
return a;
return b;
}
void ctc(int nod) {
inst[nod] = true;
st[top++] = nod;
id[nod] = low[nod] = lastid++;
for(auto it: graph[nod]) {
if(id[it] == 0)
ctc(it);
if(inst[it])
low[nod] = min(low[nod], low[it]);
}
if(low[nod] == id[nod]) {
int tmp;
vector<int> conex;
do {
tmp = st[--top];
inst[tmp] = false;
conex.push_back(tmp);
} while(tmp != nod);
tare.push_back(conex);
}
}
int main() {
int n, m, a, b;
FILE *fin = fopen("ctc.in", "r");
fscanf(fin, "%d%d", &n, &m);
for(int i = 0; i < m; ++i) {
fscanf(fin, "%d%d", &a, &b);
graph[a].push_back(b);
}
fclose(fin);
ctc(1);
FILE *fout = fopen("ctc.out", "w");
fprintf(fout, "%d\n", tare.size());
for(int i = 0; i < tare.size(); ++i) {
for(int j = 0; j < tare[i].size(); ++j)
fprintf(fout, "%d ", tare[i][j]);
fprintf(fout, "\n");
}
fclose(fout);
return 0;
}