C++解决强联通问题

简单写一个Tarjan算法。

#include <iostream>
#include <vector>
using  namespace std;int node;
int edge;
int graph[100][100];
int visited[100];
int pre[100];
int path[100][100];void init()
{for(int i = 0;i < node;i++){pre[i] = i;}
}void update_pre(int n)
{for(int i = 0;i < node;i++){if(graph[n][i] == 1 && path[n][i] == 0){pre[n] = min(pre[n], pre[i]);}}
}void remove(int n)
{for(int i = 0;i < node;i++){path[n][i] = path[i][n] = 0;}
}void dfs(int n)
{visited[n] = 1;for(int i = 0;i < node;i++){if(visited[i] == 0 && graph[n][i] == 1){path[n][i] = path[i][n] = 1;dfs(i);}}update_pre(n);remove(n);
}void print()
{for(int i = 0;i < node;i++){cout << pre[i] << " ";}
}int main()
{cin >> node >> edge;for(int i = 1;i <= edge; i++){int n1, n2;cin >> n1 >> n2;graph[n1][n2] = 1;graph[n2][n1] = 1;}init();dfs(0);print();system("pause");return 0;
}/*
8 9
0 1
1 2
2 3
3 0
2 4
4 5
6 4
5 6
6 7
*/