3560 Graph’s Cycle Component
Graph’s Cycle Component 광 도 를 사용 하여 연결 여 부 를 우선 판단 하고 링 의 각 정점 의 도 는 모두 2 이 며 연결 분량 의 각 정점 의 도가 2 인지 판단 하여 링 여 부 를 판단 한다.깊이 우선 스 택 넘 침 을 사용 하여 연결 여 부 를 판단 할 수 있 습 니 다.
- #include<stdio.h>
- #include<stdlib.h>
- #define N 100005
- typedef struct arc_node{
- int adjvex;
- struct arc_node *next;
- }arc_node;
- typedef struct vex_node{
- int color;
- int degree; //
- arc_node *first_arc;
- }vex_node;
- vex_node vertex[N];
- int flag[N]; // i
- int queue[N]; //
-
- int init(int n)
- {
- int i;
- for (i = 0; i < n; i++)
- {
- vertex[i].color = 0;
- vertex[i].degree = 0;
- vertex[i].first_arc = NULL;
- }
- return 1;
- }
- int insert(int u, int v)
- {
- arc_node *p;
- p = (arc_node *)malloc(sizeof(arc_node));
- if (!p)
- exit(0);
- p->adjvex = v;
- p->next = vertex[u].first_arc;
- vertex[u].first_arc = p;
- vertex[u].degree++;
-
- p = (arc_node *)malloc(sizeof(arc_node));
- if (!p)
- exit(0);
- p->adjvex = u;
- p->next = vertex[v].first_arc;
- vertex[v].first_arc = p;
- vertex[v].degree++;
- return 1;
- }
- int bfs(int u, int count)
- {
- arc_node *p;
- int begin, end;
- int tag; //tag 0 , 1
-
- begin = 0;
- end = 0;
- queue[end++] = u;
- flag[u] = 1;
- if (vertex[u].degree == 2)
- tag = 0;
- else
- tag = 1;
- while (begin < end)
- {
- u = queue[begin++];
- p = vertex[u].first_arc;
- while (p)
- {
- if (flag[p->adjvex] == 0)
- {
- queue[end++] = p->adjvex;
- flag[p->adjvex] = 1;
- if (vertex[p->adjvex].degree != 2)
- tag = 1; //
- }
- p = p->next;
- }
- }
- if (tag == 0)
- return 1;
- else
- return 0;
- }
- void main()
- {
- int m, n;
- int u, v;
- int i;
- int count, num;
- // freopen("input.txt", "r", stdin);
- while (scanf("%d%d", &n, &m) != EOF && !(n == 0 && m == 0))
- {
- init(n);
- for (i = 0; i < m; i++)
- {
- scanf("%d%d", &u, &v);
- insert(u, v);
- }
- for (i = 0; i < n; i++)
- {
- flag[i] = 0;
- }
- count = 0; //count
- num = 0; //num
- for (i = 0; i < n; i++)
- {
- if (flag[i] == 0)
- {
-
- count++;
- if (bfs(i, count) == 1)
- num++;
- }
- }
- printf("%d %d
", count, num);
- }
- }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
양식 제출 후 제출 버튼 비활성화텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.