Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- #define _CRT_SECURE_NO_WARNINGS
- #include <stdio.h>
- #include <stdlib.h>
- typedef struct TNode {
- int count_neighbours;
- int *neighbours;
- int sv_comp;
- } TNode;
- TNode *nodes;
- int n;
- int get_next_vertex() { // libo neproidenoj vershiny, ili vse vershiny proideny
- int i;
- for (i = 1; i <= n; i++)
- if (nodes[i].sv_comp == 0)
- return i;
- return -1;
- }
- void dfs(int cur, int comp_svyaz)
- {
- int i, neigh_id;
- TNode *neigh;
- nodes[cur].sv_comp = comp_svyaz; // tekushej vershine prisvaivaem componentu svyazi
- for (i = 0; i < nodes[cur].count_neighbours; i++)
- {
- neigh_id = nodes[cur].neighbours[i];//berem soseda tekushej vershiny
- neigh = &nodes[neigh_id]; //ukazatel na adress vershiny etogo soseda
- if (neigh->sv_comp == 0) //ne proideno
- dfs(neigh_id, comp_svyaz);
- }
- }
- void insert_svyaz(int from, int to)
- {
- TNode *cur_node = &nodes[from]; // ukazatel na nachal'nuyu vershinu rebra
- cur_node->count_neighbours++; //shitaem kolichestvo sosedei
- cur_node->neighbours = (int*) realloc(cur_node->neighbours, cur_node->count_neighbours * sizeof(int));//videliaem pamiat na kazhdogo soseda
- cur_node->neighbours[cur_node->count_neighbours - 1] = to;
- }
- int main()
- {
- int i, next_start, cur_comp_svyaz;
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int m;
- scanf("%d %d", &n, &m);
- nodes = (TNode*) calloc(n+1, sizeof(TNode));
- for (i = 0; i < m; i++)
- {
- int num1, num2;
- scanf("%d %d", &num1, &num2);
- insert_svyaz(num1, num2);
- insert_svyaz(num2, num1);
- }
- cur_comp_svyaz = 0;
- while (1)
- {
- next_start = get_next_vertex();
- if (next_start == -1) break;
- cur_comp_svyaz++;
- dfs(next_start, cur_comp_svyaz);
- }
- printf("%d\n", cur_comp_svyaz);
- for (i = 1; i <= n; i++)
- printf("%d ", nodes[i].sv_comp);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement