若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1217: Dominos 2

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,138

题目描述

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 input contains one integer specifying the number of test cases 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.

输出

For each test case, output a line containing one integer, the total number of dominos that fall over.

样例输入

1
3 2 1
1 2
2 3
2

样例输出

2

参考代码

#include <stdio.h>
#include <string.h>
#define N 1100000
char toppled[N];
int edges[N][2];
unsigned se[N];
char incoming[N];
int topple(int x) 
{
    if(!toppled[x]) 
    {
        int i;
        toppled[x] = 1;
        for (i = se[x]; i < N && edges[i][0] == x; i++) 
        {
            topple(edges[i][1]);
        }
    }
}
int comp(const int *e1, const int *e2) 
{
    return *e1 - *e2;
}
char seen[N];
int nextfin;
int finish[N];
void dfs(int n) 
{
    if(!seen[n]) 
    {
        int i;
        seen[n] = 1;
        for (i = se[n]; i < N && edges[i][0] == n; i++) 
        {
            dfs(edges[i][1]);
        }
        finish[n] = ++nextfin;
    }
}
int fincomp(const int *e1, const int *e2) 
{
    return finish[*e2] - finish[*e1];
}
int nums[N];
int main() 
{
    int CASES;
    scanf("%d", &CASES);
    while(CASES--) 
    {
        int n, m, i, cnt,l;
        memset(toppled,0,sizeof(toppled));
        memset(incoming,0,sizeof(incoming));
        memset(seen,0,sizeof(seen));
        memset(finish,0,sizeof(finish));
        scanf("%d %d %d", &n, &m, &l);
        for (i=0; i<m; i++) 
        {
            int x, y;
            scanf("%d %d", &x, &y);
            x--;
            y--;
            edges[i][0] = x;
            edges[i][1] = y;
            incoming[y] = 1;
        }
        qsort(edges, m, sizeof(edges[0]), comp);
        memset(se,-1,sizeof(se));
        for (i=m-1; i>=0; i--) 
        {
            se[edges[i][0]] = i;
        }
        for (i=0;i<l;i++) 
        {
            int x;
            scanf("%d", &x);
            x--;
            topple(x);
        }
        cnt = 0;
        for (i=0;i<n;i++) if(toppled[i]) cnt++;
        printf("%dn", cnt);
    }
    return 0;
}

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip 原站点 Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist