/* O(e^2): for each edge uv, find shortest paths from v to neighbors of u not passing through the closed neighborhood of u,
if any of them is non-trivial, we have a hole. */
#include <stdio.h>
#include <stdlib.h>
struct e
{
int to;
struct e *next, *prev, *opp;
};
static int n;
static int amark;
static struct vertex
{
struct e ns;
int target, dist, mark;
struct e *from;
} *gr;
static int *queue;
static int qb, ql;
static struct e *
add_half (int x, int y)
{
struct e *nw = malloc (sizeof (struct e));
nw->to = y;
nw->next = gr[x].ns.next;
nw->prev = &gr[x].ns;
nw->next->prev = nw;
nw->prev->next = nw;
return nw;
}
static void
add_edge (int x, int y)
{
struct e *e1 = add_half (x, y);
struct e *e2 = add_half (y, x);
e1->opp = e2;
e2->opp = e1;
}
static void
tgt_nbrs_of (int v, int t)
{
struct e *ae;
for (ae = gr[v].ns.next; ae->to != -1; ae = ae->next)
gr[ae->to].target = t;
gr[v].target = t;
}
static int
find_nontrivial_path (int f, int *tgt)
{
amark++;
qb = 0;
ql = 1;
queue[0] = f;
gr[f].from = NULL;
gr[f].dist = 0;
gr[f].mark = amark;
while (ql)
{
int v = queue[qb++];
struct e *ae;
ql--;
for (ae = gr[v].ns.next; ae->to != -1; ae = ae->next)
{
if (gr[ae->to].mark == amark)
continue;
gr[ae->to].mark = amark;
gr[ae->to].from = ae->opp;
gr[ae->to].dist = gr[v].dist + 1;
if (gr[ae->to].target)
{
if (gr[ae->to].dist > 1)
{
*tgt = ae->to;
return 1;
}
}
else
{
queue[qb + ql] = ae->to;
ql++;
}
}
}
return 0;
}
static void
print_path (int v)
{
for (; gr[v].from != NULL; v = gr[v].from->to)
printf (" %d", v + 1);
printf (" %d\n", v + 1);
}
int main (void)
{
int m, i, x, y;
struct e *ae;
scanf ("%d %d", &n, &m);
gr = malloc (n * sizeof (struct vertex));
queue = malloc (n * sizeof (int));
for (i = 0; i < n; i++)
{
gr[i].ns.to = -1;
gr[i].ns.prev = gr[i].ns.next = gr[i].ns.opp = &gr[i].ns;
gr[i].target = gr[i].dist = gr[i].mark = 0;
gr[i].from = NULL;
}
for (i = 0; i < m; i++)
{
scanf ("%d %d", &x, &y);
add_edge (x - 1, y - 1);
}
for (i = 0; i < n; i++)
{
tgt_nbrs_of (i, 1);
for (ae = gr[i].ns.next; ae->to != -1; ae = ae->next)
if (find_nontrivial_path (ae->to, &x))
{
printf ("%d", i + 1);
print_path (x);
return 0;
}
tgt_nbrs_of (i, 0);
}
printf ("no\n");
return 0;
}
Compilation message
indcyc.c: In function 'main':
indcyc.c:113:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &n, &m);
^~~~~~~~~~~~~~~~~~~~~~~
indcyc.c:126:7: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &x, &y);
^~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
256 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
384 KB |
Output is correct |
2 |
Correct |
12 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
76 ms |
656 KB |
Output is correct |
2 |
Correct |
6 ms |
640 KB |
Output is correct |
3 |
Correct |
13 ms |
896 KB |
Output is correct |
4 |
Correct |
262 ms |
840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
640 KB |
Output is correct |
2 |
Correct |
92 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
288 ms |
5120 KB |
Output is correct |
2 |
Correct |
63 ms |
2304 KB |
Output is correct |
3 |
Execution timed out |
1092 ms |
5120 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
115 ms |
2432 KB |
Output is correct |
2 |
Execution timed out |
1092 ms |
2304 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
326 ms |
10232 KB |
Output is correct |
2 |
Execution timed out |
1094 ms |
10108 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |