結果
問題 | No.2464 To DAG |
ユーザー |
👑 |
提出日時 | 2023-09-08 22:13:36 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 144 ms / 2,000 ms |
コード長 | 1,273 bytes |
コンパイル時間 | 786 ms |
コンパイル使用メモリ | 30,080 KB |
実行使用メモリ | 39,296 KB |
最終ジャッジ日時 | 2024-06-26 15:18:19 |
合計ジャッジ時間 | 13,161 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
ソースコード
#include <stdio.h> typedef struct Edge { struct Edge *next; int v, id; } edge; int DFS(edge *adj[], int flag[], int par[][2], int done[], int u) { int w, x; edge *p; while (adj[u] != NULL) { p = adj[u]; adj[u] = p->next; if (flag[p->id] != 0 || done[p->v] != 0) continue; w = p->v; if (par[w][0] == 0) { par[w][0] = u; par[w][1] = p->id; x = DFS(adj, flag, par, done, w); if (x != 0 && x != u) return x; } else { flag[p->id] = 1; while (u != w) { flag[par[u][1]] = 1; x = par[u][0]; par[u][0] = 0; par[u][1] = 0; u = x; } return w; } } done[u] = 1; return 0; } int main() { int i, N, M, u, w, a[300001], b[300001]; edge *adj[300001] = {}, e[300001], *p; scanf("%d %d", &N, &M); for (i = 1; i <= M; i++) { scanf("%d %d", &u, &w); a[i] = u; b[i] = w; e[i].v = w; e[i].id = i; e[i].next = adj[u]; adj[u] = &(e[i]); } int flag[300001] = {}, par[300001][2] = {}, done[300001] = {}; for (u = 1; u <= N; u++) { if (done[u] != 0) continue; par[u][0] = u; DFS(adj, flag, par, done, u); } int m = 0; for (i = 1; i <= M; i++) if (flag[i] == 0) m++; printf("%d %d\n", N, m); for (i = 1; i <= M; i++) if (flag[i] == 0) printf("%d %d\n", a[i], b[i]); fflush(stdout); return 0; }