图的基本应用（洛谷题单）
图的基本应用参考书籍《深入浅出程序设计竞赛》参考题单点击链接更新中…P5318 【深基18.例3】查找文献图的两种遍历方式工具递归和队列复杂度O ( n m ) O(nm)O(nm)#includebits/stdc.h#defineMAXN100005usingnamespacestd;intn,m;vectorintp[MAXN];boolu[MAXN];boolv[MAXN];queueintq;voiddfs(intx){coutx ;for(inti0;ip[x].size();i){if(!u[p[x][i]]){u[p[x][i]]true;dfs(p[x][i]);}}}voidbfs(){q.push(1);v[1]true;while(!q.empty()){intxq.front();q.pop();coutx ;for(inti0;ip[x].size();i){if(!v[p[x][i]]){v[p[x][i]]true;q.push(p[x][i]);}}}}signedmain(){cinnm;for(inti1;im;i){intx,y;cinxy;p[x].push_back(y);}for(inti1;in;i)sort(p[i].begin(),p[i].end());//若有多篇文章可以参阅先看编号小的那篇u[1]true;dfs(1);puts();bfs();return0;}P5318 【深基18.例3】查找文献题意对于每个点v vv求A ( v ) A(v)A(v)表示从点v vv出发能到达的编号的最大点方法反向建边从大编号搜索复杂度O ( n m ) O(nm)O(nm)#includebits/stdc.h#defineMAXN100005usingnamespacestd;intn,m;vectorintp[MAXN];inta[MAXN];voiddfs(intx,intv){a[x]v;for(inti0;ip[x].size();i){if(!a[p[x][i]])dfs(p[x][i],v);}}signedmain(){cinnm;for(inti1;im;i){intx,y;cinxy;p[y].push_back(x);//加反向边}for(intin;i;i--)if(!a[i])dfs(i,i);for(inti1;in;i)couta[i] ;return0;}P1113 [USACO02FEB] 杂务给定一个DAG求DAG的最长链动态规划的思想复杂度O ( n m ) O(nm)O(nm)#includebits/stdc.h#defineMAXN10010usingnamespacestd;intn,x,y,ans,len[MAXN],vis[MAXN];vectorintlinker[MAXN];intdfs(intx){if(vis[x])returnvis[x];for(inti0;ilinker[x].size();i)vis[x]max(vis[x],dfs(linker[x][i]));vis[x]len[x];returnvis[x];}signedmain(){cinn;for(inti1;in;i){cinxlen[i];while(ciny,y){linker[y].push_back(x);}}coutdfs(1)endl;return0;}
