#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ță list l[MAX_M]; // Noduri din listele de adiacență, alocate static int index[MAX_N]; // Indicii nodurilor, în ordinea descoperii int scc[MAX_N], numScc; // scc[u] este numărul CTC din care face parte u int stack[MAX_N], ss; // Stiva de noduri încă nerepartizate în CTC bool b[MAX_N]; // Diverse utilizări int n; int nextIndex; // Următorul indice disponibil /* Îl adaugă pe v la lista de adiacență a lui u, folosind poziția pos din lista statică. */ void addEdge(int u, int v, int pos) { l[pos].v = v; l[pos].next = adj[u]; adj[u] = pos; } /** * Parcurge recursiv un nod. * Returnează indicele minim la care poate ajunge un nod din subarborele lui u. * b[u] reține dacă nodul u este pe stivă. **/ int dfs(int u) { int v, minPtr; index[u] = minPtr = nextIndex++; stack[ss++] = u; // Pune nodul pe stivă b[u] = true; for (int pos = adj[u]; pos != NIL; pos = l[pos].next) { v = l[pos].v; if (index[v] == NIL) { int minPtrV = dfs(v); minPtr = MIN(minPtr, minPtrV); } else if (b[v]) { minPtr = MIN(minPtr, index[v]); } } if (minPtr == index[u]) { // Dacă u nu poate urca mai sus de u, atunci el este rădăcina unei CTC // Scoate CTC de pe stivă și o etichetează do { v = stack[--ss]; b[v] = false; scc[v] = numScc; } while (v != u); numScc++; } return minPtr; } 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] = index[i] = NIL; } for (int i = 0; i < m; i++) { fscanf(f, "%d %d", &u, &v); addEdge(u - 1, v - 1, i); } fclose(f); // Calculăm scc[], vectorul de componente conexe for (u = 0; u < n; u++) { if (index[u] == NIL) { dfs(u); } } // Restul este contabilitate. // Traversăm listele de adiacență și aflăm care din componente NU au muchii incidente. // b[i] reține dacă componenta i poate conține noduri-mamă for (int i = 0; i < numScc; i++) { b[i] = true; } for (u = 0; u < n; u++) { for (int pos = adj[u]; pos != NIL; pos = l[pos].next) { v = l[pos].v; if (scc[u] != scc[v]) { b[scc[v]] = false; } } } // Numărăm câte componente nu au muchii incidente. int numFreeScc = 0, motherScc; for (int i = 0; i < numScc; i++) { if (b[i]) { numFreeScc++; motherScc = i; } } f = fopen("matroid.out", "w"); if (numFreeScc == 1) { // Există o componentă-mamă; numărăm și listăm toate nodurile ei. int sccSize = 0; for (u = 0; u < n; u++) { if (scc[u] == motherScc) { sccSize++; } } fprintf(f, "%d\n", sccSize); for (u = 0; u < n; u++) { if (scc[u] == motherScc) { fprintf(f, "%d\n", 1 + u); } } } else { // Nu există noduri-mamă. fprintf(f, "0\n"); } fclose(f); }