Pagini recente » Cod sursa (job #1906999) | Cod sursa (job #1868416) | Cod sursa (job #3291847) | Cod sursa (job #1107809) | Cod sursa (job #1833683)
#include <cstdio>
#include <ctype.h>
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
}fin("ctc.in");
const int MAX_N = 100000;
const int MAX_M = 200000;
int last[1+MAX_N], next[1+MAX_M], mc[1+MAX_M], index[1+MAX_N], low[1+MAX_N];
int st[MAX_N], top;
int ind, comp;
int sol[1+MAX_N], topS;
bool inSt[1+MAX_N];
int min(int a, int b) {
if(a < b)
return a;
return b;
}
void ctc(int node) {
++ind;
low[node] = index[node] = ind;
st[top] = node; ++top;
inSt[node] = true;
int i = last[node];
while(i != 0) {
if(index[mc[i]] == 0) {
ctc(mc[i]);
low[node] = min(low[node], low[mc[i]]);
} else if(inSt[mc[i]])
low[node] = min(low[node], low[mc[i]]);
i = next[i];
}
if(index[node] == low[node]) {
comp++;
while(st[top - 1] != node) {
sol[topS] = st[top - 1];
low[st[top - 1]] = low[node];
inSt[st[top - 1]] = false; ++topS;
--top;
}
inSt[node] = false;
--top;
sol[topS] = node; ++topS;
}
}
int main() {
int n, m, a, b, c;
fin >> n >> m;
for(int i = 1; i <= m; ++i) {
fin >> a >> b;
mc[i] = b;
next[i] = last[a];
last[a] = i;
}
for(int i = 1; i <= n; ++i)
if(index[i] == 0)
ctc(i);
FILE *fout = fopen("ctc.out", "w");
fprintf(fout, "%d\n", comp);
c = low[sol[0]];
for(int i = 0; i < n; ++i) {
if(low[sol[i]] != c) {
c = low[sol[i]];
fprintf(fout, "\n");
}
fprintf(fout, "%d ", sol[i]);
}
fclose(fout);
return 0;
}
//problema e completa cand e bagata si parsarea