owned this note
owned this note
Published
Linked with GitHub
# CSES GRAPH ALGORITHMS
# [Counting Rooms](https://cses.fi/problemset/task/1192)
給你圖讓你判連通塊，對每個新遇到的點dfs和她連通的點，開vis維護每個位置是否被dfs到，$cnt$紀錄答案。
複雜度 : $O(V+E)=O(nm)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
vector<vector<bool>> vec;
long long ans=0;
vector<pair<int,int>> dir={{0,1},{1,0},{0,-1},{-1,0}};
inline void dfs(int y,int x){
vec[y][x]=true;
for(int i = 0;i<4;i++){
if(vec[y+dir[i].first][x+dir[i].second])continue;
dfs(y+dir[i].first,x+dir[i].second);
}
return ;
}
int main(){
cin.tie(nullptr)->sync_with_stdio(0);cout.tie(0);
int n,m;
char tmp;
cin>>n>>m;
vec.assign(n+2,vector<bool>(m+2,true));
for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)cin>>tmp,vec[i][j]=(tmp=='#');
for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)if(!vec[i][j])dfs(i,j),ans++;
cout<<ans;
}
```
:::
# [Labyrinth](https://cses.fi/problemset/task/1193)
直接bfs，vis過的不用走，紀錄從哪個點走過來。
複雜度 : $O(V+E)=O(nm)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int ax,ay,bx,by;
int main(){
cin.tie(nullptr)->sync_with_stdio(0);cout.tie(0);
pair<int,int> dir[4]={{1,0},{0,1},{-1,0},{0,-1}};
int n,m;
cin>>n>>m;
vector<vector<bool>> vec(n+2,vector<bool>(m+2,false));
char c;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cin>>c;
vec[i][j]=(c!='#');
if(c=='A')ay=i,ax=j;
else if(c=='B')by=i,bx=j;
}
}
vector<vector<int>> d(n+2,vector<int>(m+2,0));
d[ay][ax]=0;
queue<pair<int,int>> q;
q.push({ax,ay});
for(pair<int,int> tmp;!q.empty();){
tmp=q.front(),q.pop();
for(int i = 0;i<4;i++){
int nowx=tmp.first+dir[i].first,nowy=tmp.second+dir[i].second;
if(!vec[nowy][nowx])continue;
vec[nowy][nowx]=false;
d[nowy][nowx]=i+1;
q.push({nowx,nowy});
}
}
if(!d[by][bx]){
cout<<"NO";
return 0;
}
string s="";
char ans[4]={'R','D','L','U'};
while(bx!=ax||by!=ay){
s+=ans[d[by][bx]-1];
int tmpy=by-dir[d[by][bx]-1].second,tmpx=bx-dir[d[by][bx]-1].first;
by=tmpy,bx=tmpx;
}
cout<<"YES"<<'\n'<<s.size()<<'\n';
for(int i = s.size()-1;i>=0;i--)cout<<s[i];
}
```
:::
# [Building Roads](https://cses.fi/problemset/task/1666)
給你一張圖，讓你把它變成聯通圖。
$dsu$判就好，最多只有n-1條邊要加，所以可以$O(n)$判。
複雜度 : $O(V \alpha (V))$
:::spoiler code:
這餘切的毒瘤扣 不要學
```cpp=
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using i64 = long long;
using p2i = pair<int, int>;
using p2l = pair<i64, i64>;
struct DSU {
int ___;
vector<int> ____;
DSU(int _) :___(_), ____(_ + 1, -1) {}
inline int _________(int _)
{ return ____[_] < 0 ? _ : (____[_] = _________(____[_])); }
inline void _____(int _, int __) {
_ = _________(_), __ = _________(__);
if (_ == __) return;
if (____[_] > ____[__]) swap(_, __);
____[_] += ____[__];
____[__] = _;
--___;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m; cin >> n >> m;
DSU _(n);
for (int a, b; m--; ) {
cin >> a >> b;
_._____(a, b);
}
cout << _.___ - 1 << '\n';
vector<int> ans;
for (int i = 1; i <= n; i++) if (_.____[i] < 0) ans.emplace_back(i);
for (int i = 1; i < ans.size(); i++) cout << ans[0] << ' ' << ans[i] << '\n';
return 0;
}
```
:::
# [Message Route](https://cses.fi/problemset/task/1667)
問你固定s和t的最短路，因為邊權相同，bfs直接做就好。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> vec(n+1);
vector<int> dist(n+1,0),dad(n+1,0),ans;
vector<bool> chk(n+1,false);
for(int a,b,i=0;i<m;i++)cin>>a>>b,vec[a].emplace_back(b),vec[b].emplace_back(a);
queue<int> q;
q.push(1);
chk[1]=true;
dist[1]=1;
for(int tmp;!q.empty();){
tmp=q.front(),q.pop();
for(const int& i:vec[tmp]){
if(!chk[i]){
chk[i]=true;
dist[i]=dist[tmp]+1;
dad[i]=tmp;
q.push(i);
}
}
}
if(!chk[n])return cout<<"IMPOSSIBLE",0;
cout<<dist[n]<<'\n';
for(int i = 0,ed=n;i<dist[n];i++)ans.emplace_back(ed),ed=dad[ed];
for(int i = ans.size()-1;i>=0;i--)cout<<ans[i]<<' ';
}
```
:::
# [Building Teams](https://cses.fi/problemset/task/1668)
bfs著色，要是有人已經著過色了而且著的色和現在要給他著的色不同就燒雞。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
int n,m;
cin>>n>>m;
vector<vector<int>> vec(n+1);
vector<int> team(n+1,0);
vector<bool> chk(n+1,false);
for(int a,b,i=0;i<m;i++)cin>>a>>b,vec[a].emplace_back(b),vec[b].emplace_back(a);
queue<int> q;
for(int i = 1;i<=n;i++){
if(!chk[i]){
team[i]=1;
q.push(i);
for(int tmp;!q.empty();){
tmp=q.front(),q.pop();
for(const int& i:vec[tmp]){
if(chk[i]&&team[i]==team[tmp])return cout<<"IMPOSSIBLE",0;
if(!chk[i])q.push(i);
chk[i]=true;
team[i]=!(team[tmp]-1)+1;
}
}
}
}
for(int i = 1;i<=n;i++)cout<<(team[i]?team[i]:1)<<' ';
}
```
:::
# [Round Trip](https://cses.fi/problemset/task/1669/)
找一個環，輸出他。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
int n,m,ans;
cin>>n>>m;
vector<vector<int>> vec(n+1);
vector<int> dad(n+1,0);
vector<bool> chk(n+1,0);
bool flag=false;
for(int a,b,i=0;i<m;i++)cin>>a>>b,vec[a].emplace_back(b),vec[b].emplace_back(a);
function<void(int,int)> dfs=[&](int now,int last)-> void {
for(const int& i:vec[now]){
if(flag)return ;
if(i==last)continue;
dad[i]=now;
if(chk[i]){
flag=true;
ans=i;
return;
}
chk[i]=true;
dfs(i,now);
chk[i]=false;
}
};
for(int i = 1;i<=n;i++)if(!dad[i])dfs(i,0);
if(!flag)return cout<<"IMPOSSIBLE",0;
vector<int> ret;
for(int now=dad[ans];now!=ans;now=dad[now])ret.emplace_back(now);
cout<<ret.size()+2<<'\n'<<ans<<' ';
for(int i = ret.size()-1;i>=0;i--)cout<<ret[i]<<' ';
cout<<ans;
}
```
:::
# [Monsters](https://cses.fi/problemset/task/1194)
裸的多點源bfs，但@cot7302會，偏強。
複雜度 : $O(V+E)=O(nm)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define F .first
#define S .second
int n,m,dis[1004][1004];
queue<PII> q;
PII A,from[1004][1004];
inline void chk(const PII& p1,const PII& p2){if(dis[p2 F][p2 S]>dis[p1 F][p1 S]+1)dis[p2 F][p2 S]=dis[p1 F][p1 S]+1,q.push(p2),from[p2 F][p2 S]=p1;}
bool possible=false;
string s;
void track(const PII& now){
PII p=from[now F][now S];
if(p==PII(0,0))return;
if(p F==now F+1)s+="U";
else if(p F==now F-1)s+="D";
if(p S==now S+1)s+="L";
else if(p S==now S-1)s+="R";
track(p);
}
inline void bfs(bool which){
for(PII tmp,nxt;!q.empty();){
tmp=nxt=q.front(),q.pop();
nxt F++,chk(tmp,nxt),nxt F-=2,chk(tmp,nxt),nxt S++,nxt F++,chk(tmp,nxt),nxt S-=2,chk(tmp,nxt);
if(which&&(tmp F==1||tmp F==n||tmp S==1||tmp S==m)){
possible=true;
track(tmp);
return ;
}
}
}
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
char c;
cin>>n>>m;
for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++){
dis[i][j]=10000000;
cin>>c;
if(c=='#')dis[i][j]=0;
if(c=='M')q.push({i,j}),dis[i][j]=0;
else if(c=='A')A={i,j};
}
bfs(0),q.push(A),dis[A F][A S]=0,from[A F][A S]={0,0},bfs(1);
if(!possible){
cout<<"NO";
return 0;
}
cout<<"YES\n"<<s.size()<<'\n';
reverse(s.begin(),s.end());
cout<<s;
}
```
:::
# [Shortest Routes I](https://cses.fi/problemset/task/1671)
單點源最短路，邊權全為正，直接dijkstra。
複雜度 : $O((V+E) \log (V+E))$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
ll pt,val;
edge(){}
edge(const ll& tpt,const ll& tval):pt(tpt),val(tval){}
friend bool operator<(const edge& N1,const edge& N2){
return N1.val>N2.val;
}
};
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
int n,m;
cin>>n>>m;
priority_queue<edge> pq;
vector<vector<edge>> vec(n+1);
vector<ll> dist(n+1,LLONG_MAX);
dist[1]=0;
vector<bool> visit(n+1,false);
for(ll l,r,val;m--;){
cin>>l>>r>>val;
vec[l].emplace_back(r,val);
}
pq.push(edge(1,0LL));
for(edge tmp;!pq.empty();){
tmp=pq.top(),pq.pop();
if(visit[tmp.pt])continue;
visit[tmp.pt]=true;
for(const edge& e:vec[tmp.pt]){
if(e.val+tmp.val>=dist[e.pt])continue;
dist[e.pt]=e.val+tmp.val;
pq.push(edge(e.pt,dist[e.pt]));
}
}
for(int i = 1;i<=n;i++)cout<<dist[i]<<' ';
}
```
:::
# [Shortest Routes II](https://cses.fi/problemset/task/1672)
多筆詢問，不同s和t求最短路，Floyd-Warshall模板題。
複雜度 : $O({n^3}+q)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
ll pt,val;
edge(){}
edge(const ll& tpt,const ll& tval):pt(tpt),val(tval){}
friend bool operator<(const edge& a,const edge& b){
return a.val>b.val;
}
};
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
int n,m,q;
cin>>n>>m>>q;
vector<vector<ll>> dist(n+1,vector<ll>(n+1,1e18));
for(int i = 1;i<=n;i++)dist[i][i]=0;
for(ll a,b,val;m--;){
cin>>a>>b>>val;
dist[a][b]=min(dist[a][b],val);
dist[b][a]=dist[a][b];
}
for(int k = 1;k<=n;k++){
for(int i = 1;i<=n;i++){
if(i==k)continue;
for(int j = i+1;j<=n;j++){
if(j==k)continue;
if(dist[i][j]>dist[i][k]+dist[k][j]){
dist[i][j]=dist[i][k]+dist[k][j];
dist[j][i]=dist[i][j];
}
}
}
}
for(int a,b;q--;){
cin>>a>>b;
cout<<(dist[a][b]==1e18?-1:dist[a][b])<<'\n';
}
}
```
:::
# [High Score](https://cses.fi/problemset/task/1673)
給你一張圖，邊權有正有負，求最長路。
先把邊權變號，再用bellman-ford求最短路，同時判有沒有負環。
複雜度 : $O(VE)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
vector<ll> dis;
vector<bool> vis1,vis2;
vector<vector<int>> g1,g2;
vector<pair<pair<int,int>,ll>> graph;
void dfs1(int now){
if(vis1[now])return;
vis1[now]=1;
for(const auto& i:g1[now])dfs1(i);
}
void dfs2(int now){
if(vis2[now])return;
vis2[now]=1;
for(const auto& i:g2[now])dfs2(i);
}
void solve(){
cin>>n>>m;
g1.assign(n+1,{}),g2.assign(n+1,{}),dis.assign(n+1,1e18),vis1.assign(n+1,false),vis2.assign(n+1,false);
for(ll a,b,c;m--;)cin>>a>>b>>c,graph.push_back({{a,b},-c}),g1[a].emplace_back(b),g2[b].emplace_back(a);
dfs1(1),dfs2(n);
dis[1]=0LL;
for(int i = 1;i<=n;i++){
for(const auto& j:graph){
if(dis[j.first.second]>dis[j.first.first]+j.second){
dis[j.first.second]=dis[j.first.first]+j.second;
if(i==n&&vis1[j.first.second]&&vis2[j.first.second]){
cout<<-1;
return;
}
}
}
}
cout<<-dis[n];
}
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
solve();
}
```
:::
# [Flight Discount](https://cses.fi/problemset/task/1195)
給你一次機會把路徑中一個邊的$cost$減半(下高斯)，求最短路。
dijkstra+dp。
轉移式 : $$
dp[flag][v] = flag?還沒折扣過，到v的dis : 折扣過，到v的dis
$$
答案就是$dp[1][n]$
複雜度 : $O((V+E) \log (V+E))$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
struct EDGE{
ll pt,val;
bool used=false;
EDGE(){}
EDGE(const ll& tpt,const ll& tval,const bool& tu):pt(tpt),val(tval),used(tu){}
friend bool operator<(const EDGE& a,const EDGE& b){
return a.val>b.val;
}
};
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
cin>>n>>m;
vector<vector<EDGE>> vec(n+1);
vector<vector<ll>> dis(n+1,{LLONG_MAX,LLONG_MAX});
dis[1]={0,0};
vector<bool> vis(n+1,false);
for(ll a,b,c;m--;)cin>>a>>b>>c,vec[a].emplace_back(EDGE(b,c,0));
priority_queue<EDGE> pq;
pq.push(EDGE(1,0,0));
for(EDGE tmp;!pq.empty();){
tmp=pq.top(),pq.pop();
if(dis[tmp.pt][tmp.used]!=tmp.val)continue;
for(const EDGE& e:vec[tmp.pt]){
if(!tmp.used){
if(dis[tmp.pt][0]+e.val/2<dis[e.pt][1]){
dis[e.pt][1]=dis[tmp.pt][0]+e.val/2;
pq.push(EDGE(e.pt,dis[e.pt][1],1));
}
}
if(dis[tmp.pt][tmp.used]+e.val<dis[e.pt][tmp.used]){
dis[e.pt][tmp.used]=dis[tmp.pt][tmp.used]+e.val;
pq.push(EDGE(e.pt,dis[e.pt][tmp.used],tmp.used));
}
}
}
cout<<dis[n][1];
}
```
:::
# [Cycle Finding](https://cses.fi/problemset/task/1197)
給你圖，問你有沒有負環，那不就||Bellman-Ford||。
複雜度 : $O(VE)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
vector<tuple<int,int,int>> graph;
void solve(){
cin>>n>>m;
graph.assign(n+1,{});
for(ll a,b,c;m--;)cin>>a>>b>>c,graph.emplace_back(a,b,c);
vector<ll> dist(n+1,1e18),ancest(n+1,0);
int flag=0;
for(int i = 1;i<=n;i++){
flag=0;
for(const auto& [l,r,val]:graph){
if(dist[l]+val<dist[r]){
dist[r]=dist[l]+val;
ancest[r]=l;
flag=r;
}
}
}
if(!flag){
cout<<"NO\n";
return;
}
vector<int> ans;
cout<<"YES\n";
for(int i = 0;i<n;i++)flag=ancest[flag];
for(int i = ancest[flag];;i=ancest[i]){
ans.emplace_back(i);
if(i==flag)break;
}
for(int i = ans.size();i;i--)cout<<ans[i-1]<<' ';
cout<<flag<<' ';
return;
}
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
solve();
}
```
:::
# [Flight Routes](https://cses.fi/problemset/task/1196)
跟[Flight Discount](https://cses.fi/problemset/task/1195)一樣的概念，然後第一個狀態改成「第幾短路」，答案就是$dp[k][n]$
實作時推薦用$multiset$維護dp陣列。
複雜度 : $O(K(V+E)( \log (V+E)+ \log K))$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct EDGE{
ll r,val;
EDGE(){}
EDGE(const ll& R,const ll& v):r(R),val(v){}
friend bool operator<(const EDGE& a,const EDGE& b){
return a.val>b.val;
}
};
int n,m,k;
vector<EDGE> vec[1<<17];
vector<multiset<ll>> dis(1<<17);
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
cin>>n>>m>>k;
for(ll i=0,l,r,v;i<m;i++){
cin>>l>>r>>v;
vec[l].emplace_back(EDGE(r,v));
}
priority_queue<EDGE> pq;
pq.push(EDGE(1,0)),dis[1].insert(0);
for(EDGE tmp;!pq.empty();){
tmp=pq.top(),pq.pop();
if(tmp.val>*--dis[tmp.r].end())continue;
for(const EDGE& e:vec[tmp.r]){
if(dis[e.r].size()<k){
dis[e.r].insert(tmp.val+e.val);
pq.push(EDGE(e.r,tmp.val+e.val));
}
else if(e.val+tmp.val<*--dis[e.r].end()){
dis[e.r].erase(--dis[e.r].end());
dis[e.r].insert(e.val+tmp.val);
pq.push(EDGE(e.r,e.val+tmp.val));
}
}
}
int j = 0;
for(const ll& i:dis[n]){
cout<<i<<' ';
if(++j==k)return 0;
}
}
```
:::
# [Round Trip II](https://cses.fi/problemset/task/1678)
跟[Round Trip](https://cses.fi/problemset/task/1669/)不同的只有他是有向邊，但判法其實一樣||有點不知道這題到底有甚麼存在的必要||。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
constexpr int maxN=2e5+5;
int n,m,lst[maxN];
vector<int> graph[maxN];
bitset<maxN> vis,went;
int dfs(int now){
if(vis[now])return now;
if(went[now])return 0;
vis[now]=1,went[now]=1;
for(int i:graph[now]){
lst[i]=now;
int k=dfs(i);
if(k)return k;
}
vis[now]=0;
return 0;
}
int main(){
cin.tie(nullptr)->sync_with_stdio(0);
cin>>n>>m;
for(int a,b;m--;)cin>>a>>b,graph[a].emplace_back(b);
vector<int> ans;
for(int i = 1,s=0;i<=n;i++){
if(!went[i])s=dfs(i);
if(s){
for(int i = lst[s];i!=s;i=lst[i])ans.emplace_back(i);
cout<<ans.size()+2<<'\n'<<s<<' ';
for(int i = ans.size()-1;i>=0;i--)cout<<ans[i]<<' ';
return cout<<s,0;
}
}
cout<<"IMPOSSIBLE";
}
```
:::
# [Course Schedule](https://cses.fi/problemset/task/1679)
完成$v$前要完成$u$，等同於建一條$u \to v$的有向邊，而能完成$v$的條件就是要讓全部連到$v$的人都做過，可以拓樸排序。
不可行的條件就是有點沒有被拓排到。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> graph[1<<17],deg(1<<17),order;
queue<int> q;
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
cin>>n>>m;
for(int i = 0,a,b;i<m;i++){
cin>>a>>b;
deg[b]++;
graph[a].emplace_back(b);
}
for(int i = 1;i<=n;i++)if(!deg[i])q.push(i),order.emplace_back(i);
for(int tmp;!q.empty();){
tmp=q.front(),q.pop();
for(const auto& i:graph[tmp]){
deg[i]--;
if(!deg[i])q.push(i),order.emplace_back(i);
}
}
if(order.size()<n){
cout<<"IMPOSSIBLE";
return 0;
}
for(const int& i:order)cout<<i<<' ';
}
```
:::
# [Longest Flight Route](https://cses.fi/problemset/task/1680)
拓樸排序為每個點紀錄從前面走來最長的路徑，答案就是$n$的答案。
注意判斷每條路徑是否是從$1$出發的。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;
I n,m,nxt[maxN],dp[maxN],indeg[maxN];
vector<I> adj[maxN],ans;
queue<pii> q;
I main(){
IOS
cin>>n>>m;
for(I a,b;m--;)cin>>a>>b,adj[a].emplace_back(b),indeg[b]++;
rep(i,1,n+1)if(!indeg[i])q.emplace(i,i==1);
for(pii tmp;!q.empty();){
tmp=q.front(),q.pop();
for(I i:adj[tmp F]){
if(tmp S&&dp[i]<dp[tmp F]+1)dp[i]=dp[tmp F]+1,nxt[i]=tmp F;
if(!--indeg[i])q.emplace(i,!!dp[i]||i==1);
}
}
if(!dp[n])return cout<<"IMPOSSIBLE",0;
cout<<dp[n]+1<<"\n1 ";
for(;n!=1;n=nxt[n])ans.emplace_back(n);
for(;!ans.empty();ans.pop_back())cout<<ans.back()<<' ';
}
```
:::
另解 : 存反圖對$n$做dfs，然後記憶化搜索。
小知識 : 這是我這題去年第一次做的時候的原始做法。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;
I n,m,nxt[maxN];
pii dp[maxN];
bitset<maxN> vis;
vector<I> adj[maxN],topo;
pii dfs(I now){
if(now==1)return {1,1};
if(vis[now])return dp[now];
vis[now]=1;
for(I i:adj[now]){
pii tmp=dfs(i);
if(tmp S)tmp F++;
if(tmp F>dp[now] F)swap(tmp,dp[now]),nxt[now]=i;
}
return dp[now];
}
I main(){
IOS
cin>>n>>m;
for(I a,b;m--;)cin>>a>>b,adj[b].emplace_back(a);
dfs(n);
if(!dp[n] S)return cout<<"IMPOSSIBLE",0;
cout<<dp[n] F<<"\n1 ";
for(;n!=1;n=nxt[n])topo.emplace_back(n);
for(;!topo.empty();topo.pop_back())cout<<topo.back()<<' ';
}
```
:::
# [Game Routes](https://cses.fi/problemset/task/1681)
簡單拓排dp。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5,mod=1e9+7;
I n,m,dp[maxN],indeg[maxN];
vector<I> adj[maxN];
queue<I> q;
inline void add(I& a,I b){
if((a+=b)>=mod)a-=mod;
}
I main(){
IOS
cin>>n>>m;
for(I a,b;m--;)cin>>a>>b,indeg[adj[a].emplace_back(b)]++;
dp[1]=1;
rep(i,1,n+1)if(!indeg[i])q.emplace(i);
for(I tmp;!q.empty();){
tmp=q.front(),q.pop();
for(I i:adj[tmp]){
add(dp[i],dp[tmp]);
if(!--indeg[i])q.emplace(i);
}
}
cout<<dp[n];
}
```
:::
# [Investigation](https://cses.fi/problemset/task/1202)
四個東西可以在一次dijkstra裡維護好。
推薦寫一個struct當作每個點的dp值，可以很好維護。
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5,mod=1e9+7;
int n,m;
struct EDGE{
ll r,val;
EDGE(){}
EDGE(const ll& a,const ll& b):r(a),val(b){}
friend bool operator<(const EDGE& a,const EDGE& b){
return a.val>b.val;
}
};
struct node{
ll minnode,maxnode,all,dis;
}dis[maxN];
vector<EDGE> adj[maxN];
priority_queue<EDGE> pq;
inline void add(I& a,I b){
if((a+=b)>=mod)a-=mod;
}
I main(){
cin.tie(nullptr)->sync_with_stdio(0);
cin>>n>>m;
for(ll l,r,v;m--;){
cin>>l>>r>>v;
adj[l].emplace_back(EDGE(r,v));
}
rep(i,1,n+1)dis[i].dis=INF;
pq.push(EDGE(1,0));
dis[1].all=1;
for(EDGE tmp;!pq.empty();){
tmp=pq.top(),pq.pop();
if(tmp.r==n)continue;
for(const EDGE& e:adj[tmp.r]){
if(dis[e.r].dis>tmp.val+e.val){
dis[e.r].maxnode=0,dis[e.r].minnode=INF,dis[e.r].all=0;
pq.push(EDGE(e.r,dis[e.r].dis=tmp.val+e.val));
}
if(dis[e.r].dis==tmp.val+e.val){
dis[e.r].maxnode=max(dis[e.r].maxnode,dis[tmp.r].maxnode+1);
dis[e.r].minnode=min(dis[e.r].minnode,dis[tmp.r].minnode+1);
dis[e.r].all=(dis[e.r].all+dis[tmp.r].all)%(ll)(1e9+7);
}
}
}
cout<<dis[n].dis<<' '<<dis[n].all<<' '<<dis[n].minnode<<' '<<dis[n].maxnode;
}
```
:::
# [Planets Queries I](https://cses.fi/problemset/task/1750)
給一張functional graph，$q$個queries求從$v$跳$k$步會到哪。
每個點出度=1，看到$k$的值域，稍微~~通靈~~思考一下可以發現能用倍增。
複雜度 : $O(n \log C+q \log k)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,q,grid[30][1<<18];
inline int jp(int pos,int d){
for(int i=0;d;d>>=1,i++)if(d&1)pos=grid[i][pos];
return pos;
}
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
cin>>n>>q;
for(int i = 1;i<=n;i++)cin>>grid[0][i];
for(int i = 1;i<30;i++)for(int j = 1;j<=n;j++)grid[i][j]=grid[i-1][grid[i-1][j]];
for(int a,b;q--;){
cin>>a>>b;
cout<<jp(a,b)<<'\n';
}
}
```
:::
# [Planets Queries II](https://cses.fi/problemset/task/1160)
給你functional graph，$q$筆詢問問$a$點到$b$點的距離。
先輩知識 : functional graph出來的結果會是一個以上的水母圖
可以先分case來討論。
```
1.a和b在不同連通塊 : 無解。
2.a和b在水母旁邊的同一棵樹上 : 若b是a的祖先，答案就會是深度差，反之則無解。
3.a和b在水母旁邊的不同棵樹上 : 無解。
4.a在樹上，b在環上 : 先把a走到環上，再走到b即可。
5.a在環上，b在樹上 : 無解。
6.a和b在環上 : 同4
```
1用$dsu$判。
$2$和$3$的區別是根的不同，所以可以對每個樹上的點紀錄誰是他們的根，而$2$你可以用
(1)倍增(複雜度$O(\log V)$)(2)歐拉序(複雜度$O(1)$)來判，我這份是用歐拉序
$4$和$5$單純紀錄在不在環上，這可以用拓排解決，而$4$可以幫環上每個人編號，並記錄好該環的大小，可以$O(1)$求答案。
剩下就剩實作細節了，我用$SCC$幫環編號，但好像其實沒必要。
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define I int
#define A auto
#define C char
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=2e5+5;
I n,q,cnt,tmp,scc[maxN],root[maxN],edge[maxN],dep[maxN],dsu[maxN],indeg[maxN],circlesize[maxN],in[maxN],out[maxN];
inline I find(I pos){
return dsu[pos]<0?pos:(dsu[pos]=find(dsu[pos]));
}
inline void merge(I a,I b){
a=find(a),b=find(b);
if(a==b)return ;
if(dsu[a]<dsu[b])swap(a,b);
dsu[b]+=dsu[a],dsu[a]=b;
}
vector<I> adj[maxN],order,egde[maxN];
bitset<maxN> vis,notcircle;
queue<I> topo;
void dfs1(I now){
vis[now]=1;
if(!vis[edge[now]])dfs1(edge[now]);
order.emplace_back(now);
}
void dfs2(I now,I id){
scc[now]=id;
for(I i:egde[now])if(!scc[i])dfs2(i,id);
}
void tree(I now,I last,I rt){
in[now]=++cnt;
if(now!=last)vis[now]=1;
dep[now]=dep[last]+1;
root[now]=rt;
for(I i:adj[now])tree(i,now,rt);
out[now]=cnt;
}
int main(){
IOS
cin>>n>>q;
fill(dsu,dsu+n+1,-1);
rep(i,1,n+1)cin>>tmp,edge[i]=tmp,egde[tmp].emplace_back(i),indeg[tmp]++,merge(tmp,i);
rep(i,1,n+1)if(!vis[i])dfs1(i);
reverse(order.begin(),order.end());
for(I i:order)if(!scc[i])dfs2(i,i);
rep(i,1,n+1)if(!indeg[i])topo.emplace(i);
while(!topo.empty()){
tmp=topo.front(),topo.pop();
notcircle[tmp]=1;
I i = edge[tmp];
adj[i].emplace_back(tmp);
if(!(--indeg[i]))topo.emplace(i);
}
vis.reset();
rep(i,1,n+1)if(!notcircle[i])tree(i,i,i);
rep(i,1,n+1)if(!vis[scc[i]]){
vis[scc[i]]=1;
for(I pos=scc[i],j=1;pos!=scc[i]||j;pos=edge[pos],j=0)circlesize[edge[pos]]=circlesize[pos]+1;
}
for(I a,b,dis;q--;){
cin>>a>>b;
if(find(a)!=find(b))cout<<"-1\n";
else if(!notcircle[b]){
dis=circlesize[b]-circlesize[root[a]]+circlesize[scc[b]];
if(dis>=circlesize[scc[b]])dis-=circlesize[scc[b]];
cout<<dis+dep[a]-1<<'\n';
}
else if(in[b]<=in[a]&&out[b]>=out[a]){
cout<<dep[a]-dep[b]<<'\n';
}
else cout<<"-1\n";
}
}
```
:::
# [Planets Cycles](https://cses.fi/problemset/task/1751)
又是functional graph，又要找環，所以我
又去寫$SCC$了，hehe。
詳細作法 : 存反圖，把$SCC$找出來後縮點。
對每個連通塊從環上dfs下去，每一層答案就會是`dep+環的大小`。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=2e5+5;
I n,adj[maxN],scc[maxN],cnt[maxN],ans[maxN];
vector<I> jda[maxN],G[maxN],order;
bitset<maxN> vis,rundfs;
void dfs1(I now){
vis[now]=1;
if(!vis[adj[now]])dfs1(adj[now]);
order.emplace_back(now);
}
void dfs2(I now,I id){
scc[now]=id;
cnt[id]++;
for(I i:jda[now])if(!scc[i])dfs2(i,id);
}
void dfs(I now,I val){
vis[now]=1,ans[now]=val;
for(I i:G[now])dfs(i,val+1);
}
I main(){
IOS
cin>>n;
rep(i,1,n+1)cin>>adj[i],jda[adj[i]].emplace_back(i);
rep(i,1,n+1)if(!vis[i])dfs1(i);
reverse(order.begin(),order.end());
for(I i:order)if(!scc[i])dfs2(i,i);
rep(i,1,n+1)for(I j:jda[i])if(scc[i]!=scc[j])G[scc[i]].emplace_back(scc[j]);
vis.reset();
rep(i,1,n+1)if(!vis[scc[i]]&&(cnt[scc[i]]>1||adj[i]==i))dfs(scc[i],cnt[scc[i]]);
rep(i,1,n+1)cout<<ans[scc[i]]<<' ';
}
```
:::
:::spoiler 另解：
可以發現他是functional graph，所以他會是很多環，旁邊會有很多往環裡戳的樹，所以只要拓排就可以找出所有環。
只要再進一步DFS就可以求出旁邊樹上點的深（離開環的方向）度，環上的點答案就會是環的大小，樹上的點答案就會是深度$+$往上跳跳到的環的大小。
時間複雜度：$O(V+E)$。
:::spoiler code：
```cpp=
#include <bits/stdc++.h>
using namespace std;
bitset<200001> cycle;
int indeg[200001], reach[200001], depth[200001], root[200001], cycle_size[200001];
vector<int> G[200001];
void dfs(int x, int rt) {
root[x] = rt;
for (auto to : G[x]) depth[to] = depth[x] + 1, dfs(to, rt);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n; cin >> n;
for (int i = 1; i <= n; i++) {
cin >> reach[i];
++indeg[reach[i]];
}
{
queue<int> Q;
for (int i = 1; i <= n; i++) if (indeg[i] == 0) Q.emplace(i);
for (; !Q.empty(); ) {
int x = Q.front(); Q.pop();
G[reach[x]].emplace_back(x);
if (--indeg[reach[x]] == 0) Q.emplace(reach[x]);
}
}
for (int i = 1; i <= n; i++) cycle[i] = !!indeg[i];
for (int i = 1; i <= n; i++) if (cycle[i]) dfs(i, i);
for (int i = 1; i <= n; i++) if (indeg[i]) {
for (int x = i; indeg[x]; ) {
indeg[x] = 0;
root[x] = i;
cycle_size[i]++;
x = reach[x];
}
}
for (int i = 1; i <= n; i++) cout << (cycle[i] ? cycle_size[root[i]] : depth[i] + cycle_size[root[root[i]]]) << ' ';
return 0;
}
```
:::
# [Road Reparation](https://cses.fi/problemset/task/1675)
要讓整張圖聯通的話至少要建出一棵樹，題目要求邊權和最小，所以求最小生成樹。
時間複雜度：$O((V+E) \log (V+E))$（Prim）。
:::spoiler code:
```cpp=
#include <iostream>
#include <algorithm>
#include <ranges>
#include <queue>
#include <vector>
#include <utility>
#include <functional>
using namespace std;
constexpr long inf = 1e18;
long dist[100001];
bool vis[100001];
vector<pair<int, int>> G[100001];
int N, M;
int main() {
cin >> N >> M;
for (int a, b, w; M--; ) {
cin >> a >> b >> w;
G[a].emplace_back(b, w);
G[b].emplace_back(a, w);
}
long ans = 0;
ranges::fill(dist + 2, dist + N + 1, inf);
priority_queue<pair<long, int>, vector<pair<long, int>>, greater<pair<long, int>>> pq;
pq.emplace(0, 1);
int cnt = 0;
for (; !pq.empty(); ) {
auto [d, x] = pq.top(); pq.pop();
if (vis[x]) continue;
vis[x] = 1;
ans += d;
++cnt;
for (auto [to, w] : G[x]) if (w < dist[to]) {
pq.emplace(dist[to] = w, to);
}
}
if (cnt != N) return cout << "IMPOSSIBLE", 0;
cout << ans;
}
```
:::
# [Road Construction](https://cses.fi/problemset/task/1676)
動態維護聯通塊且只有加邊$\to$ 併查集。
時間複雜度：$O(n + m\alpha (n))$。
:::spoiler code:
```cpp=
#include <iostream>
using namespace std;
struct disjoint_set {
int* _;
int _count, max_cc_size;
disjoint_set(int L) :_(new int[L + 1]), _count(L), max_cc_size(1) { fill(_ + 1, _ + L + 1, -1); }
~disjoint_set() { delete[] _; }
int root(int x) { return _[x] < 0 ? x : (_[x] = root(_[x])); }
int count() { return _count; }
void merge(int a, int b) {
a = root(a), b = root(b);
if (a == b) return;
if (_[a] >_[b]) swap(a, b);
_[a] += _[b];
max_cc_size = max(max_cc_size, -_[a]);
_[b] = a;
--_count;
}
};
int N, M;
int main() {
cin >> N >> M;
disjoint_set D(N);
for (int a, b; M--; ) {
cin >> a >> b;
D.merge(a, b);
cout << D.count() << ' ' << D.max_cc_size << '\n';
}
}
```
:::
# [Flight Routes Check](https://cses.fi/problemset/task/1682)
題目問的是所有點是否互相可達$\to$整張圖是否只有一個$SCC$。
做一次縮$SCC$之後，如果有兩塊以上的$SCC$，構解只要遍歷每條邊，如果有一條$u \to v$的邊且$u,v$在不同的SCC裡面，就輸出`u v`，不然就亂找兩個在不同SCC的節點就好。
時間複雜度：$O(V+E)$。
:::spoiler code:
```cpp=
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
bitset<100001> vis;
vector<int> G[100001], rG[100001];
int n, m, dfs_order[100001], scc_id[100001], scc_cnt;
void dfs(int x) {
static int order = 0;
vis[x] = true;
for (auto to : G[x]) if (!vis[to]) dfs(to);
dfs_order[order++] = x;
}
void sfd(int x) {
scc_id[x] = scc_cnt;
for (auto to : rG[x]) if (!scc_id[to]) sfd(to);
}
int main() {
cin >> n >> m;
for (int a, b; m--; ) {
cin >> a >> b;
G[a].emplace_back(b);
rG[b].emplace_back(a);
}
for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i);
for (int i = n; i--; ) if (!scc_id[dfs_order[i]]) ++scc_cnt, sfd(dfs_order[i]);
if (scc_cnt == 1) return cout << "YES", 0;
cout << "NO\n";
for (int i = 1; i <= n; i++) {
for (auto to : G[i]) if (scc_id[to] != scc_id[i]) return cout << to << ' ' << i, 0;
}
for (int i = 2; i <= n; i++) {
if (scc_id[1] != scc_id[i]) return cout << 1 << ' ' << i, 0;
}
__builtin_unreachable();
}
```
:::
:::spoiler 另解:
用kosaraju的想法，對隨便一個點做兩次$dfs$，一次從正圖走，一次從反圖走，如果有人不能走到那就會是答案。
複雜度 : $O(V+E)$
不吃毒聲明:我沒有吃毒用$SCC$，前面是魚切寫的
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool vis[1<<17];
vector<int> vec[1<<17][2];
void dfs(int now,bool k){for(const auto& i:vec[now][k])if(!vis[i])vis[i]=1,dfs(i,k);}
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
cin>>n>>m;
for(int a,b;m--;){
cin>>a>>b;
vec[a][0].emplace_back(b);
vec[b][1].emplace_back(a);
}
dfs(1,0);
for(int i = 2;i<=n;i++)if(!vis[i])return cout<<"NO"<<'\n'<<1<<' '<<i,0;
memset(vis,0,sizeof(vis));
dfs(1,1);
for(int i = 2;i<=n;i++)if(!vis[i])return cout<<"NO"<<'\n'<<i<<' '<<1,0;
cout<<"YES";
}
```
:::
# [Planets and Kingdoms](https://cses.fi/problemset/task/1683)
臻的是$SCC$了。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
vector<int> graph[1<<17],hparg[1<<17],vis(1<<17),topo,scc(1<<17),ans(1<<17);
void dfs(int now){
vis[now]=1;
for(const int& i:graph[now])if(!vis[i])dfs(i);
topo.emplace_back(now);
}
void sfd(int now,int ind){
scc[now]=ind;
for(const int& i:hparg[now])if(!scc[i])sfd(i,ind);
}
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
cin>>n>>m;
for(int a,b;m--;)cin>>a>>b,graph[a].emplace_back(b),hparg[b].emplace_back(a);
for(int i = 1;i<=n;i++)if(!vis[i])dfs(i);
for(auto it=topo.rbegin();it!=topo.rend();it++)if(!scc[*it])sfd(*it,*it);
for(int i = 1;i<=n;i++)if(!ans[scc[i]])ans[scc[i]]=++cnt;
cout<<cnt<<'\n';
for(int i = 1;i<=n;i++)cout<<ans[scc[i]]<<' ';
}
```
:::
# [Giant Pizza](https://cses.fi/problemset/task/1684)
每個人的條件至少有一個要達成，可以用$2-SAT$解決。
具體連邊的方法 :$$
u \to v \ 代表如果 \ u=false \ 時，v要是true
$$
可以用擴展域的想法解決，最後只要判每個東西是否矛盾就好。
而這個是用$SCC$判，對於同一個條件如果兩個節點在同一個$SCC$就代表兩種條件$(true,false)$會在同一個case裡。
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
char c1,c2;
vector<int> graph[1<<18],hparg[1<<18],topo,scc(1<<18);
bitset<(1<<18)> vis,ans;
void dfs(int now){
vis[now]=1;
for(const int& i:graph[now])if(!vis[i])dfs(i);
topo.emplace_back(now);
}
inline void sfd(int now){
scc[now]=cnt;
for(const int& i:hparg[now])if(!scc[i])sfd(i);
}
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
cin>>n>>m;
for(int i = 0,a,b;i<n;i++){
cin>>c1>>a>>c2>>b;
if(c1=='-')a=2*m-a+1;
if(c2=='-')b=2*m-b+1;
graph[2*m-a+1].emplace_back(b),graph[2*m-b+1].emplace_back(a);
hparg[a].emplace_back(2*m-b+1),hparg[b].emplace_back(2*m-a+1);
}
for(int i = 1;i<=2*m;i++)if(!vis[i])dfs(i);
for(auto it=topo.rbegin();it!=topo.rend();it++)if(!scc[*it])++cnt,sfd(*it);
for(int i = 1;i<=m;i++){
if(scc[i]==scc[2*m-i+1])return cout<<"IMPOSSIBLE",0;
ans[i]=(scc[i]>scc[2*m-i+1]);
}
for(int i = 1;i<=m;i++)cout<<(ans[i]?"+ ":"- ");
}
```
:::
# [Coin Collector](https://cses.fi/problemset/task/1686)
給你一張有向圖，每走過一個點，你可以拿走他上面全部的錢，最大化拿到的錢。
發現對於每個環，最佳解就是把整個環拿完，所以最佳解就會是縮完$SCC$後拓排$dp$。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops,inline")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define ll long long
#define pii pair<int,int>
#define lb(x) (x)&-(x)
#define F .first
#define S .second
#define rep(i,l,r) for(int i = l;i<r;i++)
#define ld long double
#define pdd pair<ld,ld>
#define INF 5e18
constexpr int maxN=1e5+1;
int n,m;
bitset<maxN> vis;
vector<int> adj[maxN],jda[maxN],graph[maxN],order;
ll scc[maxN],deg[maxN],val[maxN],dp[maxN];
queue<int> q;
void dfs1(int now){
vis[now]=1;
for(int& i:adj[now])if(!vis[i])dfs1(i);
order.emplace_back(now);
}
void dfs2(int now,int id){
scc[now]=id;
for(int& i:jda[now])if(!scc[i])dfs2(i,id);
}
int main(){
IOS
cin>>n>>m;
rep(i,1,n+1)cin>>val[i];
for(int a,b;m--;)cin>>a>>b,jda[adj[a].emplace_back(b)].emplace_back(a);
rep(i,1,n+1)if(!vis[i])dfs1(i);
vis.reset();
for(auto i=order.rbegin();i!=order.rend();i++)if(!scc[*i])dfs2(*i,*i);
rep(i,1,n+1)if(i!=scc[i])val[scc[i]]+=val[i];
rep(i,1,n+1)for(int& j:jda[i])if(scc[j]!=scc[i])graph[scc[i]].emplace_back(scc[j]),deg[scc[j]]++;
rep(i,1,n+1)if(!deg[scc[i]]&&!vis[scc[i]])q.push(scc[i]),vis[scc[i]]=1,dp[scc[i]]=val[scc[i]];
for(int tmp;!q.empty();){
tmp=q.front(),q.pop();
for(int& i:graph[tmp]){
dp[i]=max(dp[i],dp[tmp]+val[i]);
if(!(--deg[i]))q.push(i);
}
}
cout<<*max_element(dp+1,dp+n+1);
}
```
:::
# [Mail Delivery](https://cses.fi/problemset/task/1691)
找歐拉迴路。
判度數，如果有人度數是奇數那就絕對沒有解。
構解的方式是你直接跑，紀錄後序$dfs$序，最後$reverse$就好了。
:::spoiler 前序和後序的差別 :
```=
隨便構一個長的像豬尾巴(中間有一個環)的圖，再連一條邊從尾巴到頭，然後你去模擬看看前序和後序的差別。
你會發現前序要是先戳到本來應該是最後走的那條路就會燒雞，但後序不會。
因為後序存的是反的歐拉迴路，第一個丟進去的一定是走到死路，也就是本來最後走的那條。
而剩下的順序就不太重要，後序就是好的了。
```
:::
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops,inline")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define I int
#define A auto
#define C char
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;
I n,m,cnt[maxN],boss[maxN],in[maxN];
vector<pii> adj[maxN];
vector<I> order;
bitset<maxN*2> vis;
void dfs(I now){
for(int pos,id;!adj[now].empty();){
tie(pos,id)=adj[now].back(),adj[now].pop_back();
if(!vis[id])vis[id]=1,dfs(pos);
}
order.emplace_back(now);
}
inline I find(I pos){
return boss[pos]==pos?pos:(boss[pos]=find(boss[pos]));
}
inline void merge(I a,I b){
a=find(a),b=find(b);
if(a!=b)boss[b]=a;
}
int main(){
IOS
cin>>n>>m;
iota(boss,boss+n+1,0);
for(I a,b,i=0;i<m;i++)cin>>a>>b,adj[a].emplace_back(b,i),adj[b].emplace_back(a,i),in[a]++,in[b]++;
if(!in[1])return cout<<"IMPOSSIBLE",0;
rep(i,1,n+1)if(in[i]&1)return cout<<"IMPOSSIBLE",0;
dfs(1);
if(order.size()!=m+1)return cout<<"IMPOSSIBLE",0;
reverse(order.begin(),order.end());
for(I& i:order)cout<<i<<' ';
}
```
:::
# [De Bruijn Sequence](https://cses.fi/problemset/task/1692)
[de Bruijn Sequence (Graph Theory)](https://www.youtube.com/watch?v=VZvU1_oPjg0)
我是看這個懂的，這個有拓展到$k$進制的De Bruijn Sequence，但應該大同小異。
複雜度 : $O({2^n})$
:::spoiler code:
```cpp=
#include <iostream>
#include <vector>
#include <bitset>
#include <utility>
#include <tuple>
#include <algorithm>
using namespace std;
bitset<65536> vis;
vector<int> G[65536], ans;
int N, mask;
bool dfs(int x) {
vis[x] = true;
ans.emplace_back(x);
if (ssize(ans) == (1 << N)) return true;
for (auto to : G[x]) if (!vis[to]) {
if (dfs(to)) return true;
}
vis[x] = false;
return ans.pop_back(), false;
}
string to_binary(int x, int len) {
string ret;
for (; len--; x >>= 1) ret += (x & 1) ^ '0';
ranges::reverse(ret);
return ret;
}
int main() {
cin >> N;
mask = (1 << N) - 1;
int edge_count = 0;
for (int i = 0; i <= mask; i++) {
int u = (i & (mask >> 1)) << 1, v = u | 1;
if (u != i) G[i].emplace_back(u);
if (v != i) G[i].emplace_back(v);
}
dfs(0);
cout << to_binary(ans[0], N);
for (int i = 1; i < ssize(ans); i++) cout << (ans[i] & 1);
}
```
:::
# [Teleporters Path](https://cses.fi/problemset/task/1693)
有向圖的歐拉路徑，和歐拉迴路的差別只有$s$的出度和$t$的入度要是奇數，剩下的人出入度要同。
複雜度 : $O(V+E)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;
int n,m,deg[maxN];
vector<pii> adj[maxN];
vector<int> order;
bitset<maxN<<1> vis;
void dfs(int now){
for(pii tmp;!adj[now].empty();)tmp=adj[now].back(),adj[now].pop_back(),dfs(tmp F);
order.emplace_back(now);
}
int main(){
IOS
cin>>n>>m;
for(int a,b,i=0;i<m;i++)cin>>a>>b,deg[a]--,deg[b]++,adj[a].emplace_back(b,i);
if(deg[1]!=-1||deg[n]!=1)return cout<<"IMPOSSIBLE",0;
rep(i,2,n)if(deg[i])return cout<<"IMPOSSIBLE",0;
dfs(1);
if(order.size()!=m+1)return cout<<"IMPOSSIBLE",0;
for(int i = order.size();i--;)cout<<order[i]<<' ';
}
```
:::
# [Hamiltonian Flights](https://cses.fi/problemset/task/1690/)
給你一張圖，求他的漢密爾頓路徑數。
可以位元dp，狀態及轉移式就是$$
dp_{mask,i} = 你已經走過mask的每一個點，且最後在i
$$$$
dp_{mask,i} = \sum_{j \in mask \ and \ j \ != \ i} dp_{mask \oplus {2^i},j}
$$
然後如果沒寫好會tle。
(4/20)學長對不起我海旅的時候在亂寫轉移式
複雜度 : $O({V^2}{2^V})$
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr ll mod=1e9+7;
ll n,m,graph[21][21],dp[1<<20|1][21];
int main(){
cin.tie(nullptr)->sync_with_stdio(0),cout.tie(0);
cin>>n>>m;
for(int a,b;m--;)cin>>a>>b,graph[a-1][b-1]++;
dp[1][0]=1;
for(int i = 1;i<(1<<n)-1;i++)for(int j = 0;j<n;j++)
if((1<<j)&i)
for(int k = 0;k<n;k++)if(!((1<<k)&i))
(dp[(1<<k)|i][k]+=dp[i][j]*graph[j][k])%=mod;
cout<<dp[(1<<n)-1][n-1];
}
```
:::
# [Knight's Tour](https://cses.fi/problemset/task/1689)
給你$8 \times 8$的棋盤和起始點，要你構造出一組漢米爾頓路徑。
詭譎題，想了很久去看題解後發現是唬爛，把你可以走下去的點選出來，然後按照他們能走下去的點的數量由小到大dfs下去，然後就過了，還特別快。
其實感覺是能走的點的數量會越走越少，然後就很好。
複雜度 : $O(magic)$
:::spoiler code:
```cpp=
#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=1e5+5;
constexpr I fx[8]={-2,-2,-1,-1,1,1,2,2},fy[8]={-1,1,-2,2,-2,2,-1,1};
vector<pii> adj[10][10];
I ans[10][10];
inline I chk(I x,I y){
return x>0&&x<9&&y>0&&y<9&&!ans[x][y];
}
inline I cnt(I x,I y){
I ret=0;
rep(i,0,8)ret+=chk(x+fx[i],y+fy[i]);
return ret;
}
bool dfs(I x,I y,I cur=1){
ans[x][y]=cur;
if(cur==64)return 1;
vector<tuple<I,I,I>> go;
rep(i,0,8){
I tox=x+fx[i],toy=y+fy[i];
if(chk(tox,toy))go.push_back({cnt(tox,toy),tox,toy});
}
sort(all(go));
for(auto& [d,tox,toy]:go)if(dfs(tox,toy,cur+1))return 1;
ans[x][y]=0;
return 0;
}
int main(){
int n,m;
cin>>m>>n;
dfs(n,m);
rep(i,1,9)rep(j,1,9)cout<<ans[i][j]<<" \n"[j==8];
}
```
:::
# [Download Speed](https://cses.fi/problemset/task/1694/)
裸的網路最大流。
時間複雜度：$O(V^2\ E)$。
:::spoiler code:
```cpp=
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct dinic {
static constexpr inline int inf = 1e9;
struct edge {
int to;
i64 cap, flow;
};
int n, m;
vector<edge> edges;
vector<vector<int>> G;
vector<int> dis, id;
dinic(int __n, int __m) : n(__n), m(__m), edges(m << 1), G(n + 1), dis(n + 1, 0), id(n + 1, 0) {
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
edges[i << 1] = {b, c, 0};
edges[i << 1 | 1] = {a, 0, 0};
G[a].emplace_back(i << 1);
G[b].emplace_back(i << 1 | 1);
}
}
bool bfs(int s, int t) {
ranges::fill(dis, inf);
queue<int> q;
dis[q.emplace(s)] = 0;
while (!q.empty()) {
int x = q.front(); q.pop();
for (auto eid : G[x]) {
auto& [to, cap, flow] = edges[eid];
if (dis[to] == inf && flow != cap) dis[q.emplace(to)] = dis[x] + 1;
}
}
return dis[t] != inf;
}
i64 dfs(int x, int t, i64 f) {
if (x == t || f == 0) return f;
i64 ret = 0;
for (int& i = id[x]; i < ssize(G[x]); i++) {
auto& [to, cap, flow] = edges[G[x][i]];
if (dis[to] != dis[x] + 1) continue;
i64 f_to = dfs(to, t, min(f - ret, cap - flow));
if (f_to > 0) {
flow += f_to;
edges[G[x][i] ^ 1].flow -= f_to;
ret += f_to;
if (ret == f) return ret;
}
}
return ret;
}
i64 operator()(int s, int t) {
i64 flow = 0;
while (1) {
if (!bfs(s, t)) break;
ranges::fill(id, 0);
while (1) {
i64 f = dfs(s, t, 1e18);
if (f <= 0) break;
flow += f;
}
}
return flow;
}
};
int main() {
int n, m; cin >> n >> m;
cout << dinic{n, m}(1, n) << '\n';
}
```
:::
# [Police Chase](https://cses.fi/problemset/task/1695)
單位網路最小$S-T$割。因為[最大流最小割定理](https://oi-wiki.org/graph/flow/max-flow/#%E6%9C%80%E5%A4%A7%E6%B5%81%E6%9C%80%E5%B0%8F%E5%89%B2%E5%AE%9A%E7%90%86)，所以先跑一次最大流之後，在殘量網路中從原點開始DFS走還有剩餘流量的邊，這樣可以分出兩個點集，之後遍歷每一條邊，兩端在不同點集的就是割邊。
時間複雜度：$O(\min(V^{\frac{2}{3}}, E^{\frac{1}{2}})\ E)$。
:::spoiler code:
```cpp=
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct dinic {
struct edge {
int to, rc;
};
static constexpr inline int inf = 1e9;
int n;
vector<edge> edges;
vector<vector<int>> G;
vector<int> dist, id;
dinic(int __n) : n(__n), edges(), G(n), dist(n), id(n) {}
void add_edge(int from, int to, int cap) {
G[from].emplace_back(ssize(edges));
edges.emplace_back(to, cap);
G[to].emplace_back(ssize(edges));
edges.emplace_back(from, cap);
}
bool bfs(int s, int t) {
ranges::fill(dist, inf);
queue<int> q;
dist[q.emplace(s)] = 0;
while (!q.empty()) {
auto x = q.front(); q.pop();
for (auto eid : G[x]) {
auto [to, rc] = edges[eid];
if (dist[to] == inf && rc > 0) dist[q.emplace(to)] = dist[x] + 1;
}
}
return dist[t] != inf;
}
int dfs(int x, int t, int f) {
if (x == t || f == 0) return f;
int ret = 0;
for (int& i = id[x]; i < ssize(G[x]); i++) {
auto& [to, rc] = edges[G[x][i]];
if (dist[to] != dist[x] + 1) continue;
int f_to = dfs(to, t, min(f - ret, rc));
if (f_to > 0) {
rc -= f_to;
edges[G[x][i] ^ 1].rc += f_to;
ret += f_to;
if (ret == f) return ret;
}
}
return ret;
}
int operator()(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
ranges::fill(id, 0);
while (1) {
int f = dfs(s, t, inf);
if (f <= 0) break;
flow += f;
}
}
return flow;
}
vector<pair<int, int>> min_cut(int s, int t) {
this->operator()(s, t);
vector<bool> vis(n, false);
vector<pair<int, int>> ret;
auto f = [&](auto&& f, int x) -> void {
vis[x] = true;
for (auto eid : G[x]) {
auto [to, rc] = edges[eid];
if (!vis[to] && rc > 0) {
f(f, to);
}
}
};
f(f, s);
vis[t] = false;
for (int i = 0; i < n; i++) if (vis[i]) {
for (auto eid : G[i]) {
auto [to, rc] = edges[eid];
if (!vis[to]) ret.emplace_back(i, to);
}
}
return ret;
}
};
int main() {
int n, m; cin >> n >> m;
dinic Dinic(n + 1);
for (int a, b; m--; ) {
cin >> a >> b;
Dinic.add_edge(a, b, 1);
}
auto ret = Dinic.min_cut(1, n);
cout << ssize(ret) << '\n';
for (auto [a, b] : ret) cout << a << ' ' << b << '\n';
}
```
:::
# [School Dance](https://cses.fi/problemset/task/1696)
裸的二分圖匹配。可以用flow做，時間複雜度是$O(\sqrt{V}\ E)$，但是常數比較大。
:::spoiler code(Dinic):
```cpp=
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct dinic {
struct edge {
int to, rc;
};
static constexpr inline int inf = 1e9;
int n;
vector<edge> edges;
vector<vector<int>> G;
vector<int> dist, id;
dinic(int __n) : n(__n), edges(), G(n), dist(n), id(n) {}
void add_edge(int from, int to, int cap) {
G[from].emplace_back(ssize(edges));
edges.emplace_back(to, cap);
G[to].emplace_back(ssize(edges));
edges.emplace_back(from, 0);
}
bool bfs(int s, int t) {
ranges::fill(dist, inf);
queue<int> q;
dist[q.emplace(s)] = 0;
while (!q.empty()) {
auto x = q.front(); q.pop();
for (auto eid : G[x]) {
auto [to, rc] = edges[eid];
if (dist[to] == inf && rc > 0) dist[q.emplace(to)] = dist[x] + 1;
}
}
return dist[t] != inf;
}
int dfs(int x, int t, int f) {
if (x == t || f == 0) return f;
int ret = 0;
for (int& i = id[x]; i < ssize(G[x]); i++) {
auto& [to, rc] = edges[G[x][i]];
if (dist[to] != dist[x] + 1) continue;
int f_to = dfs(to, t, min(f - ret, rc));
if (f_to > 0) {
rc -= f_to;
edges[G[x][i] ^ 1].rc += f_to;
ret += f_to;
if (ret == f) return ret;
}
}
return ret;
}
int operator()(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
ranges::fill(id, 0);
while (1) {
int f = dfs(s, t, inf);
if (f <= 0) break;
flow += f;
}
}
return flow;
}
};
int main() {
int n, m, k; cin >> n >> m >> k;
dinic Dinic(1 + n + m + 1);
for (int i = 1; i <= n; i++) {
Dinic.add_edge(0, i, 1);
}
for (int i = n + 1; i <= n + m; i++) {
Dinic.add_edge(i, n + m + 1, 1);
}
for (int a, b; k--; ) {
cin >> a >> b;
Dinic.add_edge(a, b + n, 1);
}
cout << Dinic(0, n + m + 1) << '\n';
for (int i = 1; i <= n; i++) {
for (auto eid : Dinic.G[i]) {
auto [to, rc] = Dinic.edges[eid];
if (rc == 0 && to > n) cout << i << ' ' << to - n << '\n';
}
}
}
```
:::
或是寫Hopcroft-Karp，複雜度一樣。
:::spoiler code(Hopcroft-Karp):
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct Hopcroft_Karp {
static constexpr inline int inf = 1e9;
int nx, ny, dis;
vector<vector<int>> G;
vector<int> dx, dy, xlink, ylink;
vector<bool> vis;
Hopcroft_Karp(int __x, int __y) : nx(__x), ny(__y), G(__x + 1), dx(__x + 1), dy(__y + 1), xlink(__x + 1), ylink(__y + 1), vis(__y + 1) {}
void add_edge(int u, int v) {
G[u].emplace_back(v);
}
bool bfs() {
fill(begin(dx), end(dx), inf);
fill(begin(dy), end(dy), inf);
dis = inf;
queue<int> q;
for (int i = 1; i <= nx; i++) if (!xlink[i]) dx[q.emplace(i)] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto to : G[u]) if (dy[to] == inf) {
dy[to] = dx[u] + 1;
if (!ylink[to]) dis = dy[to];
else dx[q.emplace(ylink[to])] = dy[to] + 1;
}
}
return dis != inf;
}
bool dfs(int u) {
for (auto to : G[u]) if (!vis[to] && dy[to] == dx[u] + 1) {
vis[to] = true;
if (ylink[to] && dy[to] == dis) continue;
if (!ylink[to] || dfs(ylink[to])) {
xlink[u] = to, ylink[to] = u;
return true;
}
}
return false;
}
int operator()() {
int ret = 0;
while (bfs()) {
fill(begin(vis), end(vis), false);
for (int i = 1; i <= nx; i++) if (!xlink[i]) ret += dfs(i);
}
return ret;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m, k; cin >> n >> m >> k;
Hopcroft_Karp HK(n, m);
for (int a, b; k--; ) {
cin >> a >> b;
HK.add_edge(a, b);
}
cout << HK() << '\n';
for (int i = 1; i <= n; i++) if (HK.xlink[i]) cout << i << ' ' << HK.xlink[i] << '\n';
}
```
:::
當然可以正常寫二分圖匹配。
:::spoiler code:
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define INF 5e18
#define all(x) x.begin(),x.end()
#define I int
#define ll long long
#define pii pair<I,I>
#define pll pair<ll,ll>
#define F .first
#define S .second
#define ld long double
#define pdd pair<ld,ld>
#define rep(i,l,r) for(I i = l;i<r;i++)
constexpr I maxN=5e2+5;
I n,m,k;
pii match[maxN];
vector<pii> adj[maxN];
vector<pii> ans;
bitset<maxN*2> vis,use;
bool dfs(I now){
for(pii i:adj[now])if(!vis[i F]){
vis[i]=1;
if(!match[i F] F||dfs(match[i F] F))
return use[match[i F] S]=0,match[i F]={now,i S},use[i S]=1,1;
}
return 0;
}
I main(){
IOS
cin>>n>>m>>k;
for(I a,b;k--;)cin>>a>>b,adj[a].emplace_back(b,k+1);
rep(i,1,n+1)dfs(i),vis.reset();
rep(i,1,n+1)for(pii j:adj[i])if(use[j S])ans.emplace_back(i,j F);
cout<<ans.size()<<'\n';
rep(i,0,ans.size())cout<<ans[i] F<<' '<<ans[i] S<<'\n';
}
```
:::
# [Distinct Routes](https://cses.fi/problemset/task/1711)
要找出最多條從$1$出發，$n$結束的路徑，且這些路徑除了$1$和$n$以外經過的點不能重複。
稍微觀察一下就能發現跑一遍$1 \to n$的最大流就是答案了。
時間複雜度：$O(V^2\ E)$。
:::spoiler code:
```cpp=
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct dinic {
struct edge {
int to, rc;
};
static constexpr inline int inf = 1e9;
int n;
vector<edge> edges;
vector<vector<int>> G;
vector<int> dist, id;
dinic(int __n) : n(__n), edges(), G(n), dist(n), id(n) {}
void add_edge(int from, int to, int cap) {
G[from].emplace_back(ssize(edges));
edges.emplace_back(to, cap);
G[to].emplace_back(ssize(edges));
edges.emplace_back(from, 0);
}
bool bfs(int s, int t) {
ranges::fill(dist, inf);
queue<int> q;
dist[q.emplace(s)] = 0;
while (!q.empty()) {
auto x = q.front(); q.pop();
for (auto eid : G[x]) {
auto [to, rc] = edges[eid];
if (dist[to] == inf && rc > 0) dist[q.emplace(to)] = dist[x] + 1;
}
}
return dist[t] != inf;
}
int dfs(int x, int t, int f) {
if (x == t || f == 0) return f;
int ret = 0;
for (int& i = id[x]; i < ssize(G[x]); i++) {
auto& [to, rc] = edges[G[x][i]];
if (dist[to] != dist[x] + 1) continue;
int f_to = dfs(to, t, min(f - ret, rc));
if (f_to > 0) {
rc -= f_to;
edges[G[x][i] ^ 1].rc += f_to;
ret += f_to;
if (ret == f) return ret;
}
}
return ret;
}
int operator()(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
ranges::fill(id, 0);
while (1) {
int f = dfs(s, t, inf);
if (f <= 0) break;
flow += f;
}
}
return flow;
}
vector<vector<int>> distinct_routes(int s, int t) {
this->operator()(s, t);
vector<bool> vis(size(edges), false);
vector<int> tmp(1, s);
vector<vector<int>> ret;
auto f = [&](auto&& f, int x) -> bool {
tmp.emplace_back(x);
for (auto eid : G[x]) if (!(eid & 1) && !vis[eid]) {
auto [to, rc] = edges[eid];
if (rc == 0) vis[eid] = true;
else continue;
if (to == t && rc == 0) {
tmp.emplace_back(t);
return true;
}
if (rc == 0) if (f(f, to)) {
return true;
}
}
tmp.pop_back();
return false;
};
for (auto eid : G[s]) if (!(eid & 1)) {
auto [to, rc] = edges[eid];
if (to == t && rc == 0) {
ret.emplace_back(vector{s, t});
continue;
}
if (rc == 0) {
if (f(f, to)) {
ret.emplace_back(tmp);
tmp.clear();
tmp.emplace_back(s);
continue;
}
}
}
return ret;
}
};
int main() {
int n, m; cin >> n >> m;
dinic Dinic(n + 1);
for (int a, b; m--; ) {
cin >> a >> b;
Dinic.add_edge(a, b, 1);
}
auto ret = Dinic.distinct_routes(1, n);
cout << size(ret) << '\n';
for (auto& v : ret) {
cout << size(v) << '\n';
for (auto x : v) cout << x << ' ';
cout << '\n';
}
}
```
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
