//很基础的拓扑排序题：判断是否是有环图#include #include #include #include using namespace std;vector graph[101];int indegree[101];int TuoPu(int n){queue q;for(int i=0;i{if(indegree[i]==0)q.push(i);}int ans=0;while(!q.empty()){int u=q.front();q.pop();ans++;for(int i=0;i{int v=graph[u][i];indegree[v]--;if(indegree[v]==0)q.push(v);}}return ans;}int main(){int n,m;while(cin>>n){if(n==0)break;cin>>m;memset(indegree,0,sizeof(indegree));memset(graph,0,sizeof(graph));for(int i=1;i{int f,t;cin>>f>>t;graph[f].push_back(t);indegree[t]++; }int ans=TuoPu(n);if(ans==0)coutelse cout}}

/* 只要在dijkstra遍历的时候加一个限制条件就行:不能从阵营2走到阵营1 脑瓜子清醒的时候写的，一遍过 */ #include <climits> #include<iostream> #include<queue> #include <algorithm> #include<cstring> using namespace std; const int INF=INT_MAX; struct Point { int id; int distance; int zy; Point (int...

//纯自己写的DFS，竟然一遍就成功了 #include <iostream> #include <queue> #include <algorithm> #include <climits> #include <cstring> using namespace std; int father[101]; int height[101]; void Initial()//每个点都作为根节点，高度都为0 { for(int i=0;i<101;i++) { father[i]=i; ...

//依然有点懵 #include <iostream> #include <climits> #include <vector> #include <cstring> #include <queue> using namespace std; const int INF=INT_MAX; struct Point { int id; int distance; bool operator<(const Point& p)const//放到优先队列里的元素自动排序 { re...

/*不同于最小生成树是对边排序，最短路径是对点到起点的距离排序memset可以初始化整个结构体，但只能初始化为0或-1，结构体内指针会变为NULL#includefill(arr,arr+n,要赋的值)fill不能初始化整个结构体，但可以任意赋值除数组外，vector也可以用这种方法赋值：fill(v.begin(),v.end(),要赋的值)#include先存这个vector graph[1000];//1~999//所有点的相邻点及其距离???再初始化这个int dis[200];//0~199//点到起点的距离最后BFS*/#include #include #include #include#include using namespace std;const int INF=INT_MAX;struct Point{    int id;//0~200    int distance;    bool operator    { return distance>p.distance;    }    Point (int i,int d)    {        id=i;        d=distance;    }};struct Edge{    //double from;    int to;//双向边分成了两条    int length;    Edge(int t,int l)    {        to=t;        length=l;    }};vector graph[1000];//1~999//所有点的相邻点及其距离???int dis[200];//0~199//每个点到起点的距离//BFSvoid Dijkstra(int s)//源点s{    priority_queue q;    dis[s]=0;    q.push(Point(s,dis[s]));//源点入队    while(!q.empty())    {        int u=q.top().id;//距离最小的边的点的id        q.pop();        for(int i=0;i        {            int v=graph[u][i].to;//相连点的编号            int d=graph[u][i].length;//相连点的距离 if(dis[v]>dis[u]+d)            {                dis[v]=dis[u]+d;                q.push(Point(v,dis[v]));            }        }    }}int main() {    int n,m;//点数量，边数量 while (cin >>n>>m) {        fill(dis,dis+n,INF);              memset(graph,0,sizeof(graph));//不能用fill(graph,graph+1000,0);因为fill不能初始化结构体        for(int i=1;i        {            int from,to,length; cin>>from>>to>>length;            graph[from].push_back(Edge(to,length));            graph[to].push_back(Edge(from,length));        }        int s,t;//起点，终点 cin>>s>>t;        Dijkstra(s);                if(dis[t]==INF)dis[t]=-1;        cout    }}

#include <iostream> #include <algorithm> using namespace std; struct Edge{ double from; double to; double length; bool operator<(const Edge& edge) const{ return length<edge.length; } }; Edge edge[330];//从0开始 int father[26]; int height[26]; void ...

#include <iostream> #include <algorithm> #include <cmath> using namespace std; struct Point{ double x; double y; }; Point point[100];//1~n struct Edge{ double from; double to; double length; bool operator<(const Edge& edge) const{ return le...

//已经建好路的两点间成本改为0 #include <iostream> #include <algorithm> using namespace std; struct Edge{ int from; int to; int cost; bool operator<(const Edge& e)const{//重载小于号 return cost<e.cost; } }; Edge edge[5000]; int father[100]; int height[100]; void In...

//最小生成树：边权和最小的一棵树 #include <iostream> #include<algorithm> using namespace std; struct Edge{ int from; int to; int length; bool operator<(const Edge& e)const{ return length<e.length; } }; Edge edge[5000]; int father[100]; int height[100]; void In...

//题目说人名是3个字母组成的，结果测试用例里面还有1、2个字母的人名 //这个题目思路很简单，就是磨人 #include <iostream> using namespace std; int sj[30];//在并查集的基础上，每个结点还要存通话时间 int height[30]; int father[30]; int visit[30]; int root[30];//记录哪些结点是根 int number[30];//每棵树的结点数量 long long total[30];//每棵树的总时长 string rm[30];//存各种长度的人名 int sl[30];...

//就是最原始的并查集 #include <iostream> using namespace std; int father[1000000]; int height[1000000]; int visit[1000000]; void Initial() { for(int i=0;i<1000000;i++) { father[i]=i; height[i]=0; visit[i]=0; } } int Find(int x) { if(father[x]==x)return x; ...

/* 人还挺无语的，就这也叫困难题，难度划分一点也不靠谱。这道题甚至一点难的算法思想和复杂数据结构都没用到 一开始脑瓜子嗡嗡的，不知道怎么下手，看了部分题解，感觉有的人的方法非常清晰易懂就选用了 首先这题最小的儿子作为根节点，辈份越大，高度越低，深度越小 按照输入记录每个结点的儿子和深度 然后对m组关系： 若深度高的结点能顺着自己的儿子结点找到深度低的结点，这两人就有直系关系，否则无 */ #include<iostream> #include <cstring> using namespace std; int son[30]; int depth[30...

//树： //入度除了根为0其他都为1 //只有一个根 //可以是空树 ：输入仅仅为0 0 //不能是环 1 1 1 2 2 1 #include <iostream> #include <cstring> using namespace std; int height[10000]; int father[10000]; int indegree[10000]; bool visit[10000];//记录输入的结点编号 int Find(int x) { if (x == father[x])return x; else ...

#include <iostream> using namespace std; int father[1001]; int height[1001]; void Initial(int n) { for(int i=1;i<=n;i++) { father[i]=i; height[i]=0; } } //两树合并为同一集合 void Union(int a,int b) { a=father[a]; b=father[b]; if(father[a]!=father[b]) {...