# hihoCoder week 55-1-连通性·四

hihoCoder week 55-1-连通性·四

6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6

3
1 1 1 4 5 5 5

```#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;
const int kMaxN = 20005;
const int kMaxM = 100005;
map<int, int> edge_code;
map<int, int> ans;
vector<vector<int> > graph;
vector<int> edges;
stack<int> stk;
bool visit[kMaxN];
int low[kMaxN];
int dfn[kMaxN];
int parent[kMaxN];
int n, m;
int points=0;
int HashEdge(int x, int y)
{
if (x > y)
return x * 100000 + y;
else
return y * 100000 + x;
}
void dfs(int u) {
//记录dfs遍历次序
static int counter = 0;
//记录节点u的子树数
int children = 0;
visit[u] = true;
//初始化dfn与low
dfn[u] = low[u] = ++counter;
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
int e = HashEdge(u, v);
if (ans.find(e)!=ans.end())
continue;
//节点v未被访问，则(u,v)为树边
if (!visit[v]) {
children++;
parent[v] = u;
stk.push(e);
dfs(v);
low[u] = min(low[u], low[v]);
//case (1)
if (parent[u] == 0 && children > 1) {
points++;
int tmp = -1, id = kMaxM;
vector<int> tmp_edges;
do{
tmp = stk.top();
stk.pop();
tmp_edges.push_back(tmp);
if (edge_code[tmp] < id)
id = edge_code[tmp];
} while (tmp != e);
for (int i = 0; i < tmp_edges.size(); i++)
ans.insert(make_pair(tmp_edges[i], id));
}
//case (2)
if (parent[u] != 0 && low[v] >= dfn[u]) {
points++;
int tmp = -1, id = kMaxM;
vector<int> tmp_edges;
do{
tmp = stk.top();
stk.pop();
tmp_edges.push_back(tmp);
if (edge_code[tmp] < id)
id = edge_code[tmp];
} while (tmp != e);
for (int i = 0; i < tmp_edges.size(); i++)
ans.insert(make_pair(tmp_edges[i], id));
}
}
//节点v已访问，则(u,v)为回边
else if (v != parent[u]) {
stk.push(e);
low[u] = min(low[u], dfn[v]);
}
}
}
int main()
{
scanf("%d %d", &n, &m);
graph.resize(n + 1);
int u, v,tmp;
for (int i = 1; i <= m; i++)
{
scanf("%d %d", &u, &v);
graph[u].push_back(v);
graph[v].push_back(u);
tmp = HashEdge(u, v);
edges.push_back(tmp);
edge_code.insert(make_pair(tmp, i));
}
dfs(1);
//求解最后一个连通分量
int max_tmp = kMaxM;
for (int i = 1; i <= m; i++)
{
if (ans.find(edges[i - 1]) == ans.end())
if (edge_code[edges[i - 1]] < max_tmp)
max_tmp = edge_code[edges[i - 1]];
}
printf("%dn", points + 1);
for (int i = 1; i <= m; i++)
printf("%d ", ans[edges[i - 1]] == 0 ? max_tmp : ans[edges[i - 1]]);
return 0;
}
```

# hihoCoder 1185-连通性·三

hihoCoder 1185-连通性·三
#1185 : 连通性·三

1->2->4                      total: 11
1->3->5                      total: 9
1->3->6->3->5           total: 13

6 6
2 4 3 5 4 4
1 2
2 4
1 3
3 5
3 6
6 3

13

```#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int kMaxN = 20005;
int n, m,new_n=0;
stack<int> stk;
vector<vector<int>> graph;
vector<vector<int>> new_graph;
int w[kMaxN];
int new_w[kMaxN];
int dfn[kMaxN];//DFS时的序号，如果!=0说明已经被访问过了
int low[kMaxN];
bool in_stack[kMaxN];
int belong[kMaxN];
int grass[kMaxN];
int in_degree[kMaxN];
bool visit[kMaxN];
int rs = 0;
void Tarjan(int u) {
//记录dfs遍历次序
static int counter = 0;
stk.push(u);
in_stack[u] = true;
//初始化dfn与low
dfn[u] = low[u] = ++counter;
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
//节点v未被访问
if (dfn[v] == 0) {
Tarjan(v);
low[u] = min(low[u], low[v]);
}
//节点v已访问，则(u,v)为回边
else if (in_stack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u])
{
new_n++;
int temp;
do{
temp = stk.top();
stk.pop();
new_w[new_n] += w[temp];
in_stack[temp] = false;
belong[temp] = new_n;
} while (temp != u);
}
}
void RebuildGraph()
{
//重建邻接矩阵
new_graph.resize(new_n + 1);
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < graph[i].size(); j++)
{
if (belong[i] != belong[graph[i][j]])
{
new_graph[belong[i]].push_back(belong[graph[i][j]]);//有边
in_degree[belong[graph[i][j]]]++;
}
}
}
}
int TopSort()
{
queue<int> zero_in_degree;
for (int i = 1; i <= new_n; i++)
if (in_degree[i] == 0)
zero_in_degree.push(i);
int ans = 0;
while (!zero_in_degree.empty())
{
int node = zero_in_degree.front();
zero_in_degree.pop();
if (visit[node])//点belong[1]能访问到的点才计算，否则这步不执行，grass[node]为0
grass[node] += new_w[node];
if (grass[node] > ans)
ans = grass[node];
for (int i = 0; i < new_graph[node].size(); i++)
{
int node2 = new_graph[node][i];
if (grass[node]>grass[node2])
grass[node2] = grass[node];
if (--in_degree[node2] == 0)
zero_in_degree.push(node2);
}
}
return ans;
}
//记录哪些点是belong[1]能访问到的
void Visit()
{
queue<int> q;
q.push(belong[1]);
while (!q.empty())
{
int f = q.front();
q.pop();
visit[f] = true;
for (int i = 0; i < new_graph[f].size(); i++)
q.push(new_graph[f][i]);
}
}
void DFS(int u,int g)
{
if (rs < g)
rs = g;
for (int i = 0; i < new_graph[u].size(); i++)
DFS(new_graph[u][i], g + new_w[new_graph[u][i]]);
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
graph.resize(n + 1);
for (int i = 1; i <= n; i++)
scanf("%d", &w[i]);
int u, v;
while (m--)
{
scanf("%d %d", &u, &v);
graph[u].push_back(v);
}
for (int i = 1; i <= n;i++)//每个点都要尝试一次
if (dfn[i]==0)
Tarjan(i);
RebuildGraph();
Visit();
printf("%dn", TopSort());
//深搜的方法也可以
//DFS(belong[1], new_w[belong[1]]);
//printf("%dn", rs);
return 0;
}
```

# hihoCoder 1184-连通性二·边的双连通分量

hihoCoder 1184-连通性二·边的双连通分量
#1184 : 连通性二·边的双连通分量

6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6

2
1 1 1 4 4 4

```#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;
const int kMaxN = 20005;
int n, m;
vector<vector<int>> graph;
stack<int> stk;
int visit[kMaxN];
int dfn[kMaxN];
int low[kMaxN];
int parent[kMaxN];
int belong[kMaxN];
int bridge_num=0;
void dfs(int u) {
//记录dfs遍历次序
static int counter = 0;
//记录节点u的子树数
int children = 0;
visit[u] = 1;
//初始化dfn与low
dfn[u] = low[u] = ++counter;
//将u加入栈
stk.push(u);
for (int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
//节点v未被访问，则(u,v)为树边
if (visit[v] == 0) {
children++;
parent[v] = u;
dfs(v);
low[u] = min(low[u], low[v]);
//bridge
if (low[v] > dfn[u]) {
bridge_num++;
}
}
//节点v已访问，则(u,v)为回边
else if (v != parent[u]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u])
{
int min_id = u;
vector<int> member;
while (stk.top() != u)
{
min_id = min(min_id, stk.top());
member.push_back(stk.top());
stk.pop();
}
member.push_back(u);
stk.pop();
for (int i = 0; i < member.size(); i++)
belong[member[i]] = min_id;
}
}
int main()
{
//freopen("input.txt", "r",stdin);
scanf("%d %d", &n, &m);
graph.resize(n + 1);
int u, v;
while (m--)
{
scanf("%d %d", &u, &v);
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1);
printf("%dn", bridge_num+1);
for (int i = 1; i <= n; i++)
printf("%d ", belong[i]);
return 0;
}
```

# hihoCoder week 52-1-连通性·一

hihoCoder week 52-1-连通性·一

6 7
1 2
1 3
2 3
3 4
4 5
4 6
5 6

3 4
3 4

```#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
const int kMaxN = 20005;
int n, m;
typedef struct edge
{
int x, y;
bool operator<(const edge& p)const//如果要加入到set中，需要重载<
{
return (this->x<p.x) || ((this->x == p.x) && (this->y<p.y));
}
};
set<int> points;
set<edge> edges;
vector<vector<int>> graph;
int visit[kMaxN];
int dfn[kMaxN];
int low[kMaxN];
int parent[kMaxN];
void dfs(int u) {
//记录dfs遍历次序
static int counter = 0;
//记录节点u的子树数
int children = 0;
visit[u] = 1;
//初始化dfn与low
dfn[u] = low[u] = ++counter;
for (int i = 0; i < graph[u].size();i++) {
int v = graph[u][i];
//节点v未被访问，则(u,v)为树边
if (visit[v]==0) {
children++;
parent[v] = u;
dfs(v);
low[u] = min(low[u], low[v]);
//case (1)
if (parent[u] == 0 && children > 1) {
points.insert(u);
}
//case (2)
if (parent[u] != 0 && low[v] >= dfn[u]) {
points.insert(u);
}
//bridge
if (low[v] > dfn[u]) {
edge e;
e.x = u;
e.y = v;
if (u > v)
{
e.x = v;
e.y = u;
}
edges.insert(e);
}
}
//节点v已访问，则(u,v)为回边
else if (v != parent[u]) {
low[u] = min(low[u], dfn[v]);
}
}
}
int main()
{
scanf("%d %d", &n, &m);
graph.resize(n + 1);
int u, v;
while (m--)
{
scanf("%d %d", &u, &v);
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1);
if (points.size() == 0)
printf("Null\n");
else
{
set<int>::iterator it = points.begin();
while (it != points.end())
{
printf("%d ", *it);
it++;
}
printf("\n");
}
if (edges.size() > 0)
{
set<edge>::iterator it = edges.begin();
while (it != edges.end())
{
printf("%d %d\n", (*it).x, (*it).y);
it++;
}
}
return 0;
}
```