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

# POJ 2352-Stars

POJ 2352-Stars
Stars
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 36453 Accepted: 15852
Description
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.

For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.
Sample Input
5
1 1
5 1
7 1
3 3
5 5
Sample Output
1
2
1
1
Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.
Source
Ural Collegiate Programming Contest 1999

```#include<iostream>
#include<cstdio>
using namespace std;
const int kMaxN = 32005;//NOT 15005;
int n;
int level[kMaxN];
int c[kMaxN];
int lowbit(int x)
{
return x&(-x);
}
int sum(int i)
{
int rs = 0;
while (i > 0)
{
rs += c[i];
i -= lowbit(i);
}
return rs;
}
{
while (i <= kMaxN)
{
c[i]+=val;
i += lowbit(i);
}
}
int main()
{
scanf("%d", &n);
int x, y;
for (int i = 0; i < n; i++)
{
scanf("%d %d", &x, &y);
x++;
level[sum(x)]++;