Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int a[100][100] = { 0 };
- int b[100][100] = { 0 };
- int num[100] = { 0 };
- int visit[100] = { 0 };
- int svaz[100] = { 0 };
- int n;
- //ksv - номер компоненты связности
- void dfsNum(int m[100][100], int v, int k, int ksv) {
- if (visit[v] == 0) {
- visit[v] = 1;
- num[v] = k;
- svaz[v] = ksv;
- cout << "Vertex " << v << " #" << k << "; KSV: " << ksv << endl;
- for (int i = 1; i <= n; i++) {
- if(m[v][i] == 1)
- dfsNum(m, i, k + 1, ksv);
- }
- }
- }
- void main() {
- setlocale(LC_ALL, "Russian");
- cout << "Кол-во вершин: ";
- cin >> n;
- int v1, v2;
- cin >> v1 >> v2;
- while (v1 != 0 && v2 != 0) {
- a[v1][v2] = 1;
- cin >> v1 >> v2;
- }
- //сразу транспонируем a в b:
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- b[i][j] = a[j][i];
- int maxN = 1;
- int maxI = 1;
- int ksv = 1;
- do {
- dfsNum(a, 1, maxN, ksv);
- for (int i = 1; i <= n; i++) {
- if (num[i] > maxN) {
- maxN = num[i];
- maxI = i;
- }
- }
- dfsNum(b, maxI, maxN + 1, ksv);
- ksv += 1;
- maxI += 1;
- } while (maxN < n);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement