图论 邻接链表

KaQqi

[C++] 纯文本查看 复制代码

#include <stdio.h>
#include <cstring>
const int N = 200020;
int n,m,position;
int is_gone[N];
int q[N];

struct obj
{
        int end;
        int worth;
        int next;
};

obj data[N];
int h[N];//第一个点的下标 

void add(int began,int end,int worth)
{
        data[position].end = end;
        data[position].worth = worth;
        data[position].next = h[began];
        h[began] = position++;
}

void dfs(int began_point)
{
        is_gone[began_point] = true;
        printf("%d\n",began_point);
        for(int i = h[began_point];i!= -1;i=data[i].next)
        {
                if(!is_gone[data[i].end])
                {
                        dfs(data[i].end);
                }
        }
}

void bfs()
{
        int hh,tt = 0;
        q[0] = 1;
        is_gone[1] = true;
        
        while(hh <= tt)
        {
                int t = q[hh++];
                printf("%d\n",t);
                for(int i = h[t];i!= -1;i = data[i].next)
                {
                        int j = data[i].end;
                        if(!is_gone[j])
                        {
                                is_gone[j] = true;
                                q[ ++ tt] = j;
                        }
                }
        }
}

int main()
{
        memset(h,-1,sizeof(h));
        scanf("%d %d",&n,&m);
        for(int i = 0;i<m;i++)
        {
                int began,end,worth;
                scanf("%d %d %d",&began,&end,&worth);
                add(began,end,worth);
        }
        bfs();
//        for(int i = 1;i<=n;i++)
//        {
//                printf("h[%d]:",i);
//                for(int j = h[i];j != -1;j = data[j].next)
//                {
//                        printf("-> (%d,%d)",data[j].end,data[j].worth);
//                }
//                printf("\n");
//        }
        return 0;
}

还是链表看的爽哇

附一组测试数据

[C++] 纯文本查看 复制代码

5 9
1 1 1
1 2 2
1 1 3
2 3 4
2 4 5
3 2 6
3 5 7
4 5 8
5 3 9

L浪子

不敢说完全看不懂, 不过还是不懂!

cyhcuichao

楼主是要表达什么意思呢？

phubing

不是说的图论麽。。。

狐尼克

你头像 军衔下面的字 是认真的吗？