#include #define MAX_N 100000 #define MAX_M 300000 #define NIL -1 #define MIN(X, Y) (((X) < (Y)) ? (X) : (Y)) typedef struct { int v, next; } list; int adj[MAX_N]; // capetele listelor de adiacență int adjt[MAX_N]; // idem, în graful transpus list l[MAX_M]; // noduri din listele de adiacență, alocate static bool seen[MAX_N]; // seen[u] reține dacă am vizitat nodul u în DFS int order[MAX_N]; // ordinea terminării nodurilor în primul DFS int scc[MAX_N], numScc; // scc[u] este numărul CTC din care face parte u bool isMother[MAX_N]; // Reține care componente *nu* au muchii incidente int n; int numSeen; /* Îl adaugă pe v la lista de adiacență a lui u, folosind poziția pos din lista statică. */ void addEdge(int* adj, int u, int v, int pos) { l[pos].v = v; l[pos].next = adj[u]; adj[u] = pos; } /* Transpune graful. Rescrie pointerii din l ca să nu folosească memorie suplimentară O(m). */ void transpose() { for (int u = 0; u < n; u++) { int pos = adj[u]; while (pos != NIL) { int next = l[pos].next; addEdge(adjt, l[pos].v, u, pos); pos = next; } } } /** * Parcurge recursiv un nod. Stochează în order[] nodurile în ordinea în care * le terminăm de explorat. **/ void dfs(int u) { if (!seen[u]) { seen[u] = true; for (int pos = adj[u]; pos != NIL; pos = l[pos].next) { dfs(l[pos].v); } order[numSeen++] = u; } } /** * Parcurge recursiv un nod în graful transpus și etichetează tot subarborele cu * componenta tare conexă numScc. **/ void dfst(int u) { if (!seen[u]) { seen[u] = true; scc[u] = numScc; for (int pos = adjt[u]; pos != NIL; pos = l[pos].next) { dfst(l[pos].v); } } } int main(void) { int m, u, v; FILE *f = fopen("matroid.in", "r"); fscanf(f, "%d %d", &n, &m); for (int i = 0; i < n; i++) { adj[i] = adjt[i] = NIL; } for (int i = 0; i < m; i++) { fscanf(f, "%d %d", &u, &v); addEdge(adj, u - 1, v - 1, i); } fclose(f); for (u = 0; u < n; u++) { dfs(u); } transpose(); for (u = 0; u < n; u++) { seen[u] = false; } for (int i = n - 1; i >= 0 ; i--) { if (!seen[order[i]]) { dfst(order[i]); numScc++; } } // Acum, fie componenta 0 este mamă, fie niciuna nu este. // Traversăm listele de adiacență și aflăm care din componente NU au muchii incidente. for (int i = 0; i < numScc; i++) { isMother[i] = true; } for (u = 0; u < n; u++) { for (int pos = adjt[u]; pos != NIL; pos = l[pos].next) { v = l[pos].v; if (scc[u] != scc[v]) { isMother[scc[u]] = false; // Graful este transpus, deci muchia reală este incidentă în u } } } // Numărăm câte componente nu au muchii incidente. bool otherMothers = false; // hehe for (int i = 1; i < numScc; i++) { otherMothers |= isMother[i]; } f = fopen("matroid.out", "w"); if (otherMothers) { // Nu există noduri-mamă. fprintf(f, "0\n"); } else { // Numărăm și listăm toate nodurile componentei 0. int sccSize = 0; for (u = 0; u < n; u++) { if (scc[u] == 0) { sccSize++; } } fprintf(f, "%d\n", sccSize); for (u = 0; u < n; u++) { if (scc[u] == 0) { fprintf(f, "%d\n", 1 + u); } } } fclose(f); }