Cow Ski Area G---二维图转一维+tarjan缩点

1.二维转成一维，变成点图

2.tarjan缩点，变成简单DAG，然后就像“校园网校园网--tarjan求缩点的两个经典问题-CSDN博客

变成SCC，即强连通图

3.就像上面说的，特判环，正常情况输出max{in为0的点，ou为0的点}

P1653 [USACO04DEC] Cow Ski Area G - 洛谷

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
int n,m;
int a[505][505];
vector<int> mp[250004];
int low[250004],dfn[250004],sd[250004],cnt,c;
stack<int> st;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int ou[250004],in[250004];
void tarjan(int u)
{low[u]=dfn[u]=++cnt;st.push(u);for(int v:mp[u]){if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}elseif(!sd[v]){low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]){sd[u]=++c;while(st.top()!=u){sd[st.top()]=c;st.pop();}st.pop();}
}
void dfs(int x,int y)
{int p1=(x-1)*m+y;for(int i=0;i<4;i++){int tx=x+dx[i];int ty=y+dy[i];if(tx>=1&&tx<=n&&ty>=1&&ty<=m){if(a[x][y]>=a[tx][ty]){int p2=(tx-1)*m+ty;mp[p1].push_back(p2);}}}
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>m>>n;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++)///二维转一维 {for(int j=1;j<=m;j++){dfs(i,j);}}for(int i=1;i<=n*m;i++)///tarjan缩点 {if(!dfn[i]){tarjan(i);}}if(c==1) cout<<0;///是个环 else{for(int i=1;i<=n*m;i++){for(int v:mp[i]){if(sd[i]!=sd[v]){ou[sd[i]]++;in[sd[v]]++;}}}int s1=0,s2=0;for(int i=1;i<=c;i++){if(!ou[i])	s1++;if(!in[i])  s2++;}cout<<max(s1,s2); ///DAG变SCC的经典问题 }return 0;
}