URAL 1389. Roadworks

Author: 2015-08-18

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1389

1389. Roadworks

Time limit: 1.0 second
Memory limit: 64 MB
Once upon a time there was a king. One day the king counted up the collected taxes and decided to spend the money for the road maintenance. There were N cities in that kingdom and M two-way roads connected them in such way that one could travel from a city to others using these roads. The road network was catastrophic without repairing, so the king made up his mind to repair as many roads as possible during the summer, before the money depreciated. The inhabitants of the kingdom were shocked to know that all the ways they used to go would be blocked for summer. So the king promised that at most one road from a city would be blocked. Help the king to fulfil his plan without displeasing the citizens.

Input

The first line of input contains two natural numbers N and M (2 ≤ N ≤ 105, M = N − 1), separated with a space. Each of the next M lines describes a road in the form (ai, bi), where ai and bi are numbers of the cities connected with i‘th road (1 ≤ ai, bi≤ N).

Output

The first line of output should contain the only integer K being the maximum number of roads that the king can close for maintenance without raising disorders in his kingdom. The next K lines should describe these roads in the same form as they were given in the input.

Sample

input output 
4 3
1 2
2 3
3 4
 
2
1 2
3 4
Problem Author: Dmitry Ivankov & Alexander Ipatov
Problem Source: Petrozavodsk summer training camp, August 2005.

2. 思路

M条双向路把N个城市全连通，现在要修理破旧的公路会阻塞交通，要求每个城市最多只能有一条与之相连的路处于修理状态，求最多能同时修理哪几条路。

以题目中给的sample为例，有1、2、3、4共四个城市，1与2、2与3、3与4相连。2同时和1、3相连，如要修理1和2之间的路，则由于每个城市最多只能有一条与之相连的路处于修理状态，2和3之间的路就不能再修理；而3和4之间的路可以修理。

将度为1的节点入队，对每次出队的节点v，将与v连的唯一的边e标记为“可修理”，并将与v相连的唯一的节点u从图中删除（不能再“修理”与u相连的边）；将u删除后，又会出现一些度为1的节点，将这些节点入队，重复上述过程，直到队列为空，输出标记为“可修理”的边。

3. 代码

#include <stdio.h>
#include <stdlib.h>

#define MAX_CITY_NUM 100001

typedef int RoadList[MAX_CITY_NUM][2];
typedef struct CityRecord {
    int cityId, roadId;
    struct CityRecord *next;
} City;

void solveE4g_Roadworks();
void inputRoads(RoadList roadList, int m, City *cities[], int degree[]);
void addCity(City *cities[], int id, int newCityId, int newRoadId);
void removeCity(City *cities[], int fromId, int deleteId);
void printCities(City *cities[], int n);
int cmp(const void *a, const void *b);

int main() {
    solveE4g_Roadworks();
    return 0;
}

RoadList roadList;
City *cities[MAX_CITY_NUM];
int removedRoadId[MAX_CITY_NUM], degree[MAX_CITY_NUM], oneDegreeQueue[MAX_CITY_NUM];
bool isCityProtected[MAX_CITY_NUM];
void solveE4g_Roadworks() {
    int n, m, removedRoadCnt = 0;
    scanf("%d %d", &n, &m);

    inputRoads(roadList, m, cities, degree);
    // printCities(cities, n);

    int front = 0, rear = 0;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] == 1) {
            oneDegreeQueue[rear++] = i;
        }
    }

    while (front != rear) {
        int currCityId = oneDegreeQueue[front++];
        if (isCityProtected[currCityId]) {
            continue;
        }

        City *otherCity = cities[currCityId];
        if (otherCity == NULL) {
            continue;
        }
        removedRoadId[removedRoadCnt++] = otherCity->roadId;
        int otherCityId = otherCity->cityId;
        degree[currCityId] = -1;
        isCityProtected[currCityId] = true;
        degree[otherCityId] = -1;
        isCityProtected[otherCityId] = true;

        City *connectedCity = cities[otherCityId];
        while (connectedCity != NULL) {
            int connectedCityId = connectedCity->cityId;
            if (connectedCityId == currCityId) {
                connectedCity = connectedCity->next;
                continue;
            }

            removeCity(cities, connectedCityId, otherCityId);
            --degree[connectedCityId];
            if (degree[connectedCityId] == 1) {
                oneDegreeQueue[rear++] = connectedCityId;
            }
            connectedCity = connectedCity->next;
        }

        // printf("Removed %d %d\n", currCityId, otherCityId);
        // printCities(cities, n);
        // printf("\n");
    }


    printf("%d\n", removedRoadCnt);
    qsort(removedRoadId, removedRoadCnt, sizeof(int), cmp);
    for (int i = 0; i < removedRoadCnt; ++i) {
        printf("%d %d\n", roadList[removedRoadId[i]][0], roadList[removedRoadId[i]][1]);
    }

}

void inputRoads(RoadList roadList, int m, City *cities[], int degree[]) {
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &roadList[i][0], &roadList[i][1]);
        addCity(cities, roadList[i][0], roadList[i][1], i);
        addCity(cities, roadList[i][1], roadList[i][0], i);
        ++degree[roadList[i][0]];
        ++degree[roadList[i][1]];
    }
}

void addCity(City *cities[], int id, int newCityId, int newRoadId) {
    City *newCity = new City();
    newCity->cityId = newCityId;
    newCity->roadId = newRoadId;
    newCity->next = cities[id];

    cities[id] = newCity;
}

void removeCity(City *cities[], int fromId, int deleteId) {

    if (cities[fromId]->cityId == deleteId) {
        cities[fromId] = cities[fromId]->next;
    } else {
        City *city = cities[fromId];

        while (city->next != NULL) {
            if (city->next->cityId == deleteId) {
                city->next = city->next->next;
                return;
            }
            city = city->next;
        }
    }
}

int cmp(const void *a, const void *b) {
    return *((int *)a) - *((int *)b);
}

void printCities(City *cities[], int n) {
    for (int i = 1; i <= n; ++i) {
        printf("%2d: ", i);
        City *c = cities[i];
        while (c != NULL) {
            printf("(%2d, %2d) ", c->cityId, c->roadId);
            c = c->next;
        }
        printf("\n");
    }

}