14292: 【原4292】图的遍历easy

题目

题目描述

author: Guo Linsong 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4292

Description

给定$n$个点，$m$条边的有向图，对于每个点$v$，求$f(v)$表示从点$v$出发能到达的编号最大的点(包括自己在内)。

$n,m\leq 100$

Input Format

第一行有$2$个整数$n$,$m$。 接下来$m$行，每行2个整数$u_i,v_i$,表示$u_i$到$v_i$有一条边。 点用$1,2,\cdots,n$编号。

Output Format

$n$个整数$f(1),f(2),\cdots,f(n)$.

Sample Input 1

5 5
1 3
4 1
2 5
5 3
2 1

Sample Output 1

3 5 3 4 5

Sample Input 2

5 0

Sample Output 2

1 2 3 4 5

Zsi-r's solution

#include <iostream>
#include <queue>
using namespace std;

class graph
{
private:
    struct edgeNode
    {
        int end;
        int weight;
        edgeNode *next;

        edgeNode(int e, int w, edgeNode *n = NULL)
        {
            end = e;
            weight = w;
            next = n;
        }
    };
    struct verNode
    {
        int ver;
        edgeNode *head;

        verNode(edgeNode *h = NULL) { head = h; }
    };
    verNode *verList;
    int Vers, Edges;
    int find(int v) const
    {
        for (int i = 0; i < Vers; i++)
            if (verList[i].ver == v)
                return i;
    }

public:
    graph(int vSize, int d[])
    {
        Vers = vSize;
        verList = new verNode [vSize];
        for (int i = 0; i < vSize;i++)
        {
            verList[i].ver = d[i];
        }
    }
    ~graph(){
        int i;
        edgeNode *p;
        for (i = 0; i < Vers;i++)
        {
            while((p=verList[i].head)!=NULL)
            {
                verList[i].head = p->next;
                delete p;
            }
        }
        delete[] verList;
    }

    void insert(int x,int y,int w=1)
    {
        int u = find(x), v = find(y);
        verList[u].head = new edgeNode(v, w, verList[u].head);
        ++Edges;
    }

    int bfs(int start)const
    {
        int max = 0;
        bool *visited = new bool[this->Vers];

        int currentNode;
        queue<int,deque<int>> q;
        edgeNode *p;

        for (int i=0;i<this->Vers;i++)
            visited[i] = false;

        q.push(start);
        while(!q.empty())
        {
            currentNode = q.front();
            q.pop();
            if (visited[currentNode]==true)continue;

            if (max<verList[currentNode].ver)
                max = verList[currentNode].ver;

            visited[currentNode] = true;
            p = verList[currentNode].head;
            while(p!=NULL)
            {
                if(visited[p->end]==false)q.push(p->end);
                p = p->next;
            }
        }
        return max;
    }

};

int main()
{
    int n, m, x, y;
    cin >> n >> m;
    int *templist = new int[n];
    for (int i = 0; i < n;i++)
    {
        templist[i] = i + 1;
    }
    graph g(n,templist);
    for (int i = 0; i < m;i++)
    {
        cin >> x >> y;
        g.insert(x, y);
    }

    for (int i = 0; i < n; i++)
    {
        cout << g.bfs(i)<<' ';
    }
    return 0;
}