首页 > ACM题库 > HDU-杭电 > HDU 3173-Dominos[解题报告]HOJ
2014
03-06

HDU 3173-Dominos[解题报告]HOJ

Dominos

问题描述 :

Dominos are lots of fun. Children like to stand the tiles on their side in long lines. When one domino falls, it knocks down the next one, which knocks down the one after that, all the way down the line. However, sometimes a domino fails to knock the next one down. In that case, we have to knock it down by hand to get the dominos falling again.

Your task is to determine, given the layout of some domino tiles, the minimum number of dominos that must be knocked down by hand in order for all of the dominos to fall.

输入:

The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing two integers, each no larger than 100 000. The first integer n is the number of domino tiles and the second integer m is the number of lines to follow in the test case. The domino tiles are numbered from 1 to n. Each of the following lines contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well.

输出:

The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing two integers, each no larger than 100 000. The first integer n is the number of domino tiles and the second integer m is the number of lines to follow in the test case. The domino tiles are numbered from 1 to n. Each of the following lines contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well.

样例输入:

1
3 2
1 2
2 3

样例输出:

1

//IN THE NAME OF GOD
#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <queue>
#include <map>
#include <fstream>
#include <utility>
#include <sstream>
#include <list>
#include <iomanip>
#include <functional>
#include <deque>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <complex>
#include <climits>
#include <cctype>
#include <cassert>
#include <bitset>
#include <limits>
#include <numeric>

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

#define timestamp(x) printf("Time : %.3lf s.\n", clock()*1.0/CLOCKS_PER_SEC)
#define INF 1000000000
#define pii pair < int , int >
#define MP make_pair
#define MOD 1000000007
#define EPS 1e-9
#define LL long long 
#define MAXN 200000+10

int n, m;
vector < int > AdjList[MAXN], RAdjList[MAXN];
vector < int > dfs_low, dfs_num, visited, S , numgroup , tmp ;
int dfsNumberCounter, numSCC, Z;
vector < vector < int > > group;

void tarjanSCC(int u) {
	dfs_low[u] = dfs_num[u] = dfsNumberCounter++; // dfs_low[u] <= dfs_num[u]
	S.push_back(u); // stores u in a vector based on order of visitation
	visited[u] = 1;
	for (int j = 0; j < (int)AdjList[u].size(); j++) {
		int v = AdjList[u][j];
		if (dfs_num[v] == 0 )
			tarjanSCC(v);
		if (visited[v]) // condition for update
			dfs_low[u] = min(dfs_low[u], dfs_low[v]);
	}
	if (dfs_low[u] == dfs_num[u]) { // if this is a root (start) of an SCC
		//printf("SCC %d:", ++numSCC); // this part is done after recursion
		Z++;
		tmp.clear();
		while (1) {
			int v = S.back(); S.pop_back(); visited[v] = 0;
			tmp.push_back(v);
			numgroup[v] = Z;
			if (u == v) break;
		}
		group.push_back(tmp);
		//printf("\n");
	}
}

void init(){
	dfs_low.clear(), dfs_num.clear(), visited.clear(), S.clear() , numgroup.clear() , group.clear() ;
	for (int i = 0; i < MAXN; i++) AdjList[i].clear() , RAdjList[i].clear() ;
	numSCC = 0;
	dfs_low.assign(MAXN, 0), dfs_num.assign(MAXN, 0), visited.assign(MAXN, 0), numgroup.assign(MAXN, 0);
	dfsNumberCounter = numSCC = 0;
	Z = 0;
}

int main()
{
	ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
	freopen("i.txt", "r", stdin);
	//freopen("o.txt", "w", stdout);
#endif
	int t, u, v;
	cin >> t;
	while (t--){
		cin >> n >> m;
		init();
		for (int i = 0; i < m; i++){
			cin >> u >> v;
			AdjList[u].push_back(v);
			RAdjList[v].push_back(u);
		}
		for (int i = 1 ; i <= n; i++){
			if (dfs_num[i] == 0){
				tarjanSCC(i);
			}
		}
		int f;
		for (int i = 0; i < group.size(); i++){
			f = 0;
			for (int j = 0; j < group[i].size() && !f ; j++){
				v = group[i][j];
				for (int t = 0; t < RAdjList[v].size() && !f ; t++){
					u = RAdjList[v][t];
					if (numgroup[u] != numgroup[v]) f = 1;
				}
			}
			if (!f) numSCC++;
		}
		cout << numSCC << endl;
	}
	return 0;
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的