首页 > ACM题库 > HDU-杭电 > HDU 2754-HOJ-Dominos 2[解题报告]C++
2014
02-14

HDU 2754-HOJ-Dominos 2[解题报告]C++

Dominos 2

问题描述 :

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.

Given a set of dominos that are knocked down by hand, your task is to determine the total number of dominos that fall.

输入:

The first line of each test chunk contains an integer specifying the number of test cases in this chunk to follow. Each test case begins with a line containing three integers n, m, l no larger than 10 000, followed by m+l additional lines. The first integer n is the number of domino tiles. The domino tiles are numbered from 1 to n. Each of the m lines after the first line contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well. Each of the following l lines contains a single integer z indicating that the domino numbered z is knocked over by hand.
Please process to the end of the data file.

输出:

The first line of each test chunk contains an integer specifying the number of test cases in this chunk to follow. Each test case begins with a line containing three integers n, m, l no larger than 10 000, followed by m+l additional lines. The first integer n is the number of domino tiles. The domino tiles are numbered from 1 to n. Each of the m lines after the first line contains two integers x and y indicating that if domino number x falls, it will cause domino number y to fall as well. Each of the following l lines contains a single integer z indicating that the domino numbered z is knocked over by hand.
Please process to the end of the data file.

样例输入:

1
3 2 1
1 2
2 3
2
1
3 2 1
1 2
2 3
2

样例输出:

2
2

#include <cstdlib>   
#include <cctype>   
#include <cstring>   
#include <cstdio>   
#include <cmath>   
#include <algorithm>   
#include <vector>   
#include <string>   
#include <iostream>   
#include <sstream>   
#include <map>   
#include <set>   
#include <queue>   
#include <stack>   
#include <fstream>   
#include <numeric>   
#include <iomanip>   
#include <bitset>   
#include <list>   
#include <stdexcept>   
#include <functional>   
#include <utility>   
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MEM(a,b) memset((a),(b),sizeof(a))
const int N = 10000;
vector<int> v[N + 1];
int flag[N + 1];
int cnt;

void dfs(int x)
{
	if (flag[x]) return;
	flag[x] = 1;
	cnt++;
	for (int i = 0; i < v[x].size(); i++)
	{
		dfs(v[x][i]);
	}
}
int main()
{
	
	//freopen("input.txt", "r", stdin);
	int ncase;
	while (cin >> ncase)
	{

		while (ncase--)
		{
			int n, m, l;
			cin >> n >> m >> l;
			for (int i = 1; i <= n; i++) v[i].clear();
			for (int i = 0; i < m; i++)
			{
				int x, y;
				cin >> x >> y;
				v[x].push_back(y);
			}
			MEM(flag, 0);
			cnt = 0;
			while (l--)
			{

				int x;
				cin >> x;
				dfs(x);

			}
			cout << cnt << endl;

		}
	}
	return 0;
}

  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?