# 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;
}
```