//很基础的拓扑排序题：判断是否是有环图#include <iostream>#include <queue>#include <cstring>#include <algorithm>using namespace std;vector<int> graph[101];int indegree[101];int TuoPu(int n){queue<int> q;for(int i=0;i<n;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<graph[u].size();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<=m;i++){int f,t;cin>>f>>t;graph[f].push_back(t);indegree[t]++;}int ans=TuoPu(n);if(ans==0)cout<<"NO"<<endl;else cout<<"YES"<<endl;}}

/* 只要在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 i,int d,int z) { i...

//纯自己写的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; height[i]=0; } } int Fin...

//依然有点懵 #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//放到优先队列里的元素自动排序 { return distance>p.distan...

/* 不同于最小生成树是对边排序，最短路径是对点到起点的距离排序memset可以初始化整个结构体，但只能初始化为0或-1，结构体内指针会变为NULL#include<ctring>fill(arr,arr+n,要赋的值)fill不能初始化整个结构体，但可以任意赋值除数组外，vector也可以用这种方法赋值：fill(v.begin(),v.end(),要赋的值)#include<algorithm>先存这个vector<Edge> graph[1000];//1~999//所有点的相邻点及其距离???再初始化这个int dis[200];//0~199//点到起点的距离最后BFS*/#include <iostream>#include <queue>#include <climits>#include<algorithm>#include <cstring>using namespace std;const int INF=INT_MAX;struct Point{int id;//0~200int distance;bool operator<(const Point& p)const{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<Edge> graph[1000];//1~999//所有点的相邻点及其距离???int dis[200];//0~199//每个点到起点的距离//BFSvoid Dijkstra(int s)//源点s{priority_queue<Point> q;dis[s]=0;q.push(Point(s,dis[s]));//源点入队while(!q.empty()){int u=q.top().id;//距离最小的边的点的idq.pop();for(int i=0;i<graph[u].size();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<=m;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<<dis[t]<<endl;}}

#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 Initial()//每个点都作为根节点，高度都为0 { for(...

#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 length<edge.length; } }; Edge edge...

//已经建好路的两点间成本改为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 Initial() { for(int i=0;i<100;i...

//最小生成树：边权和最小的一棵树 #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 Initial() { for(int i=0;i<100;i+...

//题目说人名是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; else return Find(father[x]); } void Union(in...

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

//树： //入度除了根为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 return Find(father[x])...

#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]) { if(height[a]>height[b])father[b]=a; else if(...