2 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int N=4100; vector<int> G[N]; int match[N], chw[N], tsp; bool findmuniu(int x) { for(int y : G[x]) if(chw[y] != tsp) { chw[y] = tsp; if( (match[y] == 0) || findmuniu(match[y]) ) { match[y] = x; return 1; } } return 0; } int cnt, low[N], dfn[N], scc[N]; stack<int> stk; bool instk[N]; void tarjan(int x) { low[x] = dfn[x] = ++tsp; stk.push(x); instk[x] = True; for(int y : G[x]) { if( dfn[y] == 0) { tarjan(y); low[x] = min(low[x], low[y]); } else if(instk[y]) low[x] = min(low[x], dfn[y]); } if( low[x] == dfn[x] ) { cnt++; for(int z = -1; z != x; ) { z = stk.top(); stk.pop(); instk[z] = 0; scc[z] = cnt; } } } int b[2100], blen; int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) { int k; scanf("%d", &k); for(int j=1, x; j<=k; j++) scanf("%d", &x), G[i].push_back(x + n); } memset(match, 0, sizeof(match)); memset(chw, 0, sizeof(chw)); tsp = 0; for(int i=1; i<=n; i++) tsp++, findmuniu(i); for(int i=1; i<=n; i++) G[i + n].push_back(match[i + n]); tsp = cnt = 0; memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn)); memset(scc, 0, sizeof(scc)); memset(instk, False, sizeof(instk)); for(int i=1; i<=n + n; i++) if(dfn[i] == 0) tarjan(i); for(int i=1; i<=n; i++) { vector<int> V; for(int j : G[i]) if(scc[i] == scc[j]) V.push_back(j); sort(V.begin(), V.end()); printf("%d ", V.size()); for(int j : V) printf("%d ", j - n); printf("\n"); } return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N=4100; vector<int>G[N]; int match[N],chw[N],tsp; bool findmuniu(int x) { for(int y:G[x]) if(chw[y]!=tsp) { chw[y]=tsp; if( (match[y]==0)||findmuniu(match[y]) ) { match[y]=x; return 1; } } return 0; } int cnt,low[N],dfn[N],scc[N]; stack<int>stk; bool instk[N]; void tarjan(int x) { low[x]=dfn[x]=++tsp; stk.push(x);instk[x]=True; for(int y:G[x]) { if( dfn[y]==0) { tarjan(y); low[x]=min(low[x],low[y]); } else if(instk[y]) low[x]=min(low[x],dfn[y]); } if( low[x]==dfn[x] ) { cnt++; for(int z=-1;z!=x;) { z=stk.top();stk.pop();instk[z]=0; scc[z]=cnt; } } } int b[2100],blen; int main() { int n;scanf("%d",&n); for(int i=1;i<=n;i++) { int k;scanf("%d",&k); for(int j=1,x;j<=k;j++)scanf("%d",&x),G[i].push_back(x+n); } memset(match,0,sizeof(match)); memset(chw,0,sizeof(chw)); tsp=0;for(int i=1;i<=n;i++)tsp++,findmuniu(i); for(int i=1;i<=n;i++)G[i+n].push_back(match[i+n]); tsp=cnt=0;memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn)); memset(scc,0,sizeof(scc));memset(instk,False,sizeof(instk)); for(int i=1;i<=n+n;i++) if(dfn[i]==0) tarjan(i); for(int i=1;i<=n;i++) { vector<int>V; for(int j:G[i])if(scc[i]==scc[j]) V.push_back(j); sort(V.begin(),V.end()); printf("%d ",V.size());for(int j:V) printf("%d ",j-n); printf("\n"); } return 0; }
- 1
信息
- ID
- 1500
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 7
- 标签
- 递交数
- 152
- 已通过
- 30
- 上传者