dfs+链式前向星存图

题目描述
牛牛擅长投影剑类来战斗，他投影的武器甚至有着核弹般的破坏力，故人送外号核弹剑仙。
现在牛牛投影了n把武器，编号为1\sim 1∼n，每把武器都有一个属于自己的破坏力，且任意两把武器之间的破坏力不同。他接下来进行了m次比较，每次比较会告诉你a武器破坏力强于b武器破坏力，数据保证比较结果不会自相矛盾。
请问你能根据这m次比较结果，告诉牛牛：对于i号武器，明确比i号武器破坏力大的武器有多少把吗？

其实这道题的正解是bitset+拓扑排序，奈何我不会（逃）

题目分析

1. 可以说这个题目用dfs和链式前向星存图来解答很形象生动，读者一看就会明白
2. 而且感觉做完这个题目竟然有一丝舒爽的感觉~
3. 具体解释看代码注释，我会一一分析

首先要做出这个题目得会前向星存图，一般的前向星都是三个变量，但是这个题目不需要边的权值，所以只需要两个就行

void add(int u, int v, int w) //链式前向星加边
{
   e[cnt].to = v;
   e[cnt].w = w;
   e[cnt].next = head[u]; //存储该点的下一条边
   head[u] = cnt++;       //更新目前该点的最后一边
}

AC代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
struct node
{
    int u, v, next;
} edge[maxn];

int vis[maxn], head[maxn], cnt, ans;

void add(int u, int v) //链式前向星加边
{
    edge[++cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int dfs(int x)
{
    for (int i = head[x]; ~i; i = edge[i].next) //遍历该点的邻接点
    {
        int v = edge[i].v; //破坏力大于该点的点
        if (vis[v])
            continue;
        vis[v] = 1;
        ++ans;  //找到一个就加一个
        dfs(v); //再去找，因为假如2>1,找到3>2，那么3肯定大于1
    }
    return ans;
}

int main()
{
    int n, m, x, y;
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &x, &y);
        add(y, x); //反向存边，把攻击力大的存在后面方便寻找
    }
    for (int i = 1; i <= n; ++i)
    {
        ans = 0; //每找一个点就更新一次
        memset(vis, 0, sizeof(vis));
        printf("%d\n", dfs(i));
    }
    return 0;
}