33DAI 33 LV 6 (1/1) SU @ 2023-6-9 15:12:30

CF1213F Unstable String Sort

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int n, k;
int p[MAXN + 5];
int q[MAXN + 5];
// 按 p[] 标记的每个点的顺序
int id[MAXN + 5];
// 反向边并查集
int fa[MAXN + 5];
int findFa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findFa(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    for (int i = 1; i <= n; i++)
        cin >> q[i];
    // 按 p[] 标顺序
    for (int i = 1; i <= n; i++)
        id[p[i]] = i;
    /*
    for (int i = 1; i <= n; i++)
        cout << id[i] << " ";
    cout << "\n";
    */
    // 检查 q 的逆序边来缩点
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= n - 1; i++)
    {
        // a[q[i]] <= a[q[i+1]]
        int u = q[i];
        int v = q[i + 1];
        int faU = findFa(u);
        int faV = findFa(v);
        // 把 v ~ u 一连串并起来
        if (id[v] < id[u] && faU != faV)
        {
            int fvid = id[faV];
            int fuid = id[faU];
            // 按id
            // id[faV] ~ id[v],                  ,id[faU]/fuid ~ id[u]
            // id[faV] ~ id[v],  ,id[faPre]~preId,id[faU]/fuid ~ id[u]
            // 按 p 里面的顺序的每个数
            // faV ~ v,          ,faPre ~ pre    ,faU ~ u
            while (fuid != fvid)
            {
                int preId = fuid - 1; // p[preId] = pre
                int faPre = findFa(p[preId]);
                fa[faU] = faPre;
                faU = faPre;
                fuid = id[faPre];
            }
        }
    }
    // 复用 id[] 存缩点后的排名 1~
    id[p[1]] = 1;
    int rnk = 1;
    for (int i = 2; i <= n; i++)
    {
        // 开缩
        if (findFa(p[i]) != p[i])
            id[p[i]] = id[p[i - 1]];
        else
            id[p[i]] = ++rnk;
    }
    if (rnk < k)
    {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for (int i = 1; i <= n; i++)
        if (id[i] < k)
            cout << (char)('a' + id[i] - 1);
        else
            cout << (char)('a' + k - 1);
    return 0;
}

0

33DAI 33 LV 6 (1/1) SU @ 2023-6-8 15:39:10

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n, m;
vector<int> edge[MAXN + 5];
bool vis[MAXN + 5], inS[MAXN + 5];
int low[MAXN + 5], num[MAXN + 5], belong[MAXN + 5], out[MAXN + 5];
int ind, resCnt;
stack<int> s;
void dfs(int u)
{
    vis[u] = true;
    low[u] = num[u] = ++ind;
    s.push(u);
    inS[u] = true;
    for (int i = 0; i < edge[u].size(); i++)
    {
        int v = edge[u][i]; //u->v;
        if (!vis[v])
        {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if (inS[v])
        {
            low[u] = min(low[u], num[v]);
        }
    }
    if (num[u] == low[u])
    {
        ++resCnt;
        while (s.top() != u)
        {
            belong[s.top()] = resCnt;
            inS[s.top()] = false;
            s.pop();
        }
        belong[u] = resCnt;
        inS[u] = false;
        s.pop();
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
            dfs(i);
    }
    for (int u = 1; u <= n; u++)
    {
        for (int i = 0; i < edge[u].size(); i++)
        {
            int v = edge[u][i];
            if (belong[u] != belong[v])
            {
                out[belong[u]]++;
            }
        }
    }
    int zero = -1;
    for (int i = 1; i <= resCnt; i++)
    {
        if (out[i] == 0)
        {
            if (zero == -1)
            {
                zero = i;
            }
            else
            {
                cout << "0";
                return 0;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (belong[i] == zero)
            ans++;
    cout << ans << endl;
    return 0;
}

0

33DAI 33 LV 6 (1/1) SU @ 2023-6-8 15:38:11

P4306 [JSOI2010]连通数

Floyd 传递闭包

#include <bits/stdc++.h>
using namespace std;
int n;
string s;
bitset<2005> e[2005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        for (int j = 0; j < s.length(); j++)
            if (s[j] == '1')
                e[i].set(j);
        e[i].set(i);
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (e[j][i])
                e[j] |= e[i];
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans += e[i].count();
    cout << ans << "\n";
    return 0;
}

缩点后拓扑排序dp

TLE

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2000;
int n;
char g[MAXN+5][MAXN+5];
vector<int> e[MAXN+5]; //原图 
vector<int> ee[MAXN+5]; //缩点后的新图
vector<int> points;//新图中的点的编号 
//缩点相关
int idx;//时间戳
int dfn[MAXN+5],low[MAXN+5];
stack<int> s;
bool inS[MAXN+5]; 
int belong[MAXN+5];//原图每个点属于缩点后的哪个点 
int cnt[MAXN+5];//缩点后的每个新点包括了几个原来的点 
//拓扑排序
int d[MAXN+5];//存缩点后的每个点反向图度数
queue<int> q; 
//求答案
int ans;//最终答案
bool flag[MAXN+5][MAXN+5];//存缩点后的新图的两点间是否相连 
void dfs(int u){
	dfn[u] = low[u] = ++idx;
	s.push(u);
	inS[u] = true;
	for(int v:e[u]){
		if(dfn[v]==0){
			dfs(v);
			low[u] = min(low[u], low[v]);
		}else if(inS[v]){
			low[u] = min(low[u], dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		//栈里面u以及u后面进去的点都属于根为u的强联通分量 
		while(s.top()!=u){
			cnt[u]++;
			belong[s.top()]=u;
			inS[s.top()]=false;
			s.pop();
		}
		cnt[u]++;
		belong[u]=u;
		inS[u]=false;
		s.pop();
	} 
} 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	//读取原图 
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>g[i][j];
	for(int u=1;u<=n;u++){
		for(int v=1;v<=n;v++){
			if(g[u][v]=='1')
				e[u].push_back(v);
		}
	}
	//原图的强连通分量缩点 
	for(int i=1;i<=n;i++)
		if(dfn[i]==0)
			dfs(i);
	/*
	for(int i=1;i<=n;i++)
		cout<<belong[i]<<" "<<cnt[i]<<endl;
	*/
	//构建新图（反图） 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			if(g[i][j]=='1')
				if(belong[i]!=belong[j]){
					ee[belong[j]].push_back(belong[i]);
					d[belong[i]]++;
					//cout<<belong[i]<<"->"<<belong[j]<<endl;
				}
		if(belong[i]==i)
			points.push_back(i);
	}
	//新图是一个dag，拓扑排序的过程中求解新图中的点连接关系 
	for(int u:points)
		if(d[u]==0)
			q.push(u);
	while(q.empty()==false){
		int u=q.front();
		q.pop();
		//cout<<u<<endl;
		for(int v:ee[u]){
			//u能到哪些点，v就也能到那些点
			for(int x:points)
				if(flag[u][x])
					flag[v][x]=true;
			flag[v][u]=true;
			//拓扑排序 
			d[v]--;
			if(d[v]==0){
				q.push(v);
			}
		}
	}
	//统计答案 
	ans=0;
	for(int u:points){
		ans+=cnt[u]*cnt[u];
		for(int v:points){
			if(flag[u][v]==true)
				ans+=cnt[u]*cnt[v];
		}
	} 
	cout<<ans<<"\n";
	return 0;
}

AC

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2000;
int n;
char g[MAXN+5][MAXN+5];
vector<int> e[MAXN+5]; //原图 
vector<int> ee[MAXN+5]; //缩点后的新图
vector<int> points;//新图中的点的编号 
//缩点相关
int idx;//时间戳
int dfn[MAXN+5],low[MAXN+5];
stack<int> s;
bool inS[MAXN+5]; 
int belong[MAXN+5];//原图每个点属于缩点后的哪个点 
int cnt[MAXN+5];//缩点后的每个新点包括了几个原来的点 
//拓扑排序
int d[MAXN+5];//存缩点后的每个点反向图度数
queue<int> q; 
//求答案
int ans;//最终答案
bitset<MAXN+5> flag[MAXN+5];//存缩点后的新图的两点间是否相连 
void dfs(int u){
	dfn[u] = low[u] = ++idx;
	s.push(u);
	inS[u] = true;
	for(int v:e[u]){
		if(dfn[v]==0){
			dfs(v);
			low[u] = min(low[u], low[v]);
		}else if(inS[v]){
			low[u] = min(low[u], dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		//栈里面u以及u后面进去的点都属于根为u的强联通分量 
		while(s.top()!=u){
			cnt[u]++;
			belong[s.top()]=u;
			inS[s.top()]=false;
			s.pop();
		}
		cnt[u]++;
		belong[u]=u;
		inS[u]=false;
		s.pop();
	} 
} 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	//读取原图 
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>g[i][j];
	for(int u=1;u<=n;u++){
		for(int v=1;v<=n;v++){
			if(g[u][v]=='1')
				e[u].push_back(v);
		}
	}
	//原图的强连通分量缩点 
	for(int i=1;i<=n;i++)
		if(dfn[i]==0)
			dfs(i);
	/*
	for(int i=1;i<=n;i++)
		cout<<belong[i]<<" "<<cnt[i]<<endl;
	*/
	//构建新图（反图） 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			if(g[i][j]=='1')
				if(belong[i]!=belong[j]){
					ee[belong[j]].push_back(belong[i]);
					d[belong[i]]++;
					//cout<<belong[i]<<"->"<<belong[j]<<endl;
				}
		if(belong[i]==i)
			points.push_back(i);
	}
	//新图是一个dag，拓扑排序的过程中求解新图中的点连接关系 
	for(int u:points)
		if(d[u]==0)
			q.push(u);
	while(q.empty()==false){
		int u=q.front();
		q.pop();
		//cout<<u<<endl;
		for(int v:ee[u]){
			//u能到哪些点，v就也能到那些点
			flag[v] = flag[v]|flag[u];
			flag[v].set(u);
			//拓扑排序 
			d[v]--;
			if(d[v]==0){
				q.push(v);
			}
		}
	}
	//统计答案 
	ans=0;
	for(int u:points){
		ans+=cnt[u]*cnt[u];
		for(int v:points){
			if(flag[u][v]==true)
				ans+=cnt[u]*cnt[v];
		}
	} 
	cout<<ans<<"\n";
	return 0;
}

缩点后记忆化搜索dp

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2000;
int n;
char g[MAXN+5][MAXN+5];
vector<int> e[MAXN+5]; //原图 
vector<int> ee[MAXN+5]; //缩点后的新图
vector<int> points;//新图中的点的编号 
//缩点相关
int idx;//时间戳
int dfn[MAXN+5],low[MAXN+5];
stack<int> s;
bool inS[MAXN+5]; 
int belong[MAXN+5];//原图每个点属于缩点后的哪个点 
int cnt[MAXN+5];//缩点后的每个新点包括了几个原来的点 
//求答案
int ans;//最终答案
bool vis[MAXN+5];//标记每个店的flag有没有求完 
bitset<MAXN+5> flag[MAXN+5];//存缩点后的新图的两点间是否相连 
void dfs(int u){
	dfn[u] = low[u] = ++idx;
	s.push(u);
	inS[u] = true;
	for(int v:e[u]){
		if(dfn[v]==0){
			dfs(v);
			low[u] = min(low[u], low[v]);
		}else if(inS[v]){
			low[u] = min(low[u], dfn[v]);
		}
	}
	if(dfn[u]==low[u]){
		//栈里面u以及u后面进去的点都属于根为u的强联通分量 
		while(s.top()!=u){
			cnt[u]++;
			belong[s.top()]=u;
			inS[s.top()]=false;
			s.pop();
		}
		cnt[u]++;
		belong[u]=u;
		inS[u]=false;
		s.pop();
	} 
} 
void getFlag(int u){
	if(vis[u]==true)
		return;
	for(int v:ee[u]){
		getFlag(v);
		flag[u] = flag[u]|flag[v];
		flag[u].set(v); 
	}
	vis[u]=true;	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	//读取原图 
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>g[i][j];
	for(int u=1;u<=n;u++){
		for(int v=1;v<=n;v++){
			if(g[u][v]=='1')
				e[u].push_back(v);
		}
	}
	//原图的强连通分量缩点 
	for(int i=1;i<=n;i++)
		if(dfn[i]==0)
			dfs(i);
	/*
	for(int i=1;i<=n;i++)
		cout<<belong[i]<<" "<<cnt[i]<<endl;
	*/
	//构建新图（正图） 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			if(g[i][j]=='1')
				if(belong[i]!=belong[j]){
					ee[belong[i]].push_back(belong[j]);
					//cout<<belong[i]<<"->"<<belong[j]<<endl;
				}
		if(belong[i]==i)
			points.push_back(i);
	}
	//新图是一个dag，拓扑排序的过程中求解新图中的点连接关系 
	for(int u:points)
		if(vis[u]==false)
			getFlag(u);
	//统计答案 
	ans=0;
	for(int u:points){
		ans+=cnt[u]*cnt[u];
		for(int v:points){
			if(flag[u][v]==true)
				ans+=cnt[u]*cnt[v];
		}
	} 
	cout<<ans<<"\n";
	return 0;
}

0

33DAI 33 LV 6 (1/1) SU @ 2023-6-7 8:25:15

P3387 【模板】缩点

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
const int MAXM = 100000;
//原图 
int n, m;
int a[MAXN + 5]; //点权
vector<int> e[MAXN + 5]; //存图
//tarjan
int idx, dfn[MAXN + 5], low[MAXN + 5];
stack<int> s; 
bool inS[MAXN + 5]; //每个点是否在栈中
//存SCC
int sccCnt;
vector<int> scc[MAXN + 5];
//新图（复用 a[] 存新图的每个点权值）
int id[MAXN + 5]; //缩到了新图的哪个点上
vector<int> ee[MAXN + 5]; //新图存边
void dfs(int u)
{
    dfn[u] = low[u] = ++idx;
    s.push(u);
    inS[u] = true;
    for (int v : e[u])
    {
        if(dfn[v] == 0)
        {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if(inS[v])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    //当前点是某个 scc 的根
    if(dfn[u] == low[u])
    {
        ++sccCnt;
        while(s.top() != u)
        {
            id[s.top()] = u, a[u] += a[s.top()]; // 缩点
            inS[s.top()] = false;
            scc[sccCnt].push_back(s.top());
            s.pop();
        }
        //处理 u
        id[s.top()] = u; // 缩点
        inS[s.top()] = false;
        scc[sccCnt].push_back(s.top());
        s.pop();
    }
}
//拓扑排序、DAG 上 DP
int f[MAXN + 5]; //走到每个点的最大权值之和
int d[MAXN + 5]; //新图的每个点入度
queue<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //输入
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
    }
    //缩点
    for(int i = 1; i <= n; i++)
        if(dfn[i] == 0)
            dfs(i);
    /*
    cout << sccCnt << "\n";
    for(int i = 1; i <= sccCnt; i++)
    {
        cout << scc[i].size() << ":";
        for(int x : scc[i])
            cout << x << " ";
        cout << "\n";
    }
    for(int i=1;i<=n;i++)
        cout << id[i] << ",\n"[i==n];
    */
    //建新图
    for(int u = 1; u <= n; u++)
        for(int v : e[u])
            if(id[u] != id[v])
            {
                ee[id[u]].push_back(id[v]);
                d[id[v]]++;
               // cout << id[u] << "~" << id[v] << "\n";
            }
    for(int i = 1; i <= n; i++)
        if(d[i] == 0)
        {
            q.push(i);
            f[i] = a[i];
        }
    int ans = -1;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        ans = max(ans, f[u]);
        for(int v : ee[u]){
            f[v] = max(f[v], f[u] + a[v]);
            d[v]--;
            if(d[v] == 0)
                q.push(v);
            
        }
    }
    cout << ans << "\n";
    return 0;
}
/*
10 20
986 587 671 143 521 985 204 36 921 990 
4 2
2 8
7 8
2 4
1 7
8 7
10 2
5 9
4 5
5 8
4 9
2 7
5 6
9 1
9 6
4 10
9 7
9 2
1 2
5 7
====
5133
*/

0

33DAI 33 LV 6 (1/1) SU @ 2023-6-6 16:46:51

P8435 【模板】点双连通分量

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
const int MAXM = 2000000;
int n, m;
//<终点坐标,边的编号>
vector<pair<int, int>> edge[MAXN + 5]; // edge[i]：与i相连的所有边
bool visE[MAXM + 5];                   // 每条边是否做过了
bool vis[MAXN + 5];                    // vis[i]: i有没有走过
int low[MAXN + 5];                     // low[i]：不经过父节点能走到的最小时间戳；
int dfn[MAXN];                         // dfn[i]：深搜生成树的时间戳
int idx;                               // idx：时间戳
stack<int> tempS;
int v_bcc_cnt;               // 点双数量
vector<int> v_bcc[MAXN + 5]; // 存所有点双
void dfs(int u, int eId)
{
    tempS.push(u);
    vis[u] = visE[eId] = true;
    low[u] = dfn[u] = ++idx;
    int childCnt = 0;
    for (int i = 0; i < edge[u].size(); i++)
    {
        int v = edge[u][i].first; // u->v;
        int uvId = edge[u][i].second;
        if (!vis[v])
        {
            childCnt++;
            dfs(v, uvId);
            low[u] = min(low[u], low[v]);
            // 根节点可以一起做，不管是不是割点，根节点都可以加入下面的点双
            if (low[v] >= dfn[u])
            {
                v_bcc_cnt++;
                while (tempS.top() != v)
                {
                    v_bcc[v_bcc_cnt].push_back(tempS.top());
                    tempS.pop();
                }
                v_bcc[v_bcc_cnt].push_back(tempS.top());
                tempS.pop();
                v_bcc[v_bcc_cnt].push_back(u);
            }
        }
        else if (!visE[uvId])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (eId == 0 && childCnt == 0)
        v_bcc[++v_bcc_cnt].push_back(u);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(make_pair(v, i));
        edge[v].push_back(make_pair(u, i));
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            idx = 0;
            dfs(i, 0);
        }
    }
    cout << v_bcc_cnt << endl;
    for (int i = 1; i <= v_bcc_cnt; i++)
    {
        cout << v_bcc[i].size() << " ";
        for (auto x : v_bcc[i])
            cout << x << " ";
        cout << endl;
    }
    return 0;
}

0

33DAI 33 LV 6 (1/1) SU @ 2023-6-6 14:52:49

P8436 【模板】边双连通分量

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
const int MAXM = 2000000;
int n, m;
//<终点坐标,边的编号>
vector<pair<int, int>> edge[MAXN + 5]; // edge[i]：与i相连的边
bool visE[MAXM + 5];                   // 每条边是否做过了
bool vis[MAXN + 5];                    // vis[i]: i有没有走过；
bool flag[MAXN + 5];                   // flag[i]：fa[i]~i 是否为桥
int low[MAXN + 5];                     // low[i]：不经过父节点能走到的最小时间戳；
int dfn[MAXN];                         // dfn[i]：深搜生成树的时间戳
int idx, resCnt;                       // idx：时间戳； resCnt：割点数量
// 并查集
int fa[MAXN + 5];
int findFa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findFa(fa[x]);
}
void merge(int x, int y)
{
    cout << endl;
    int faX = findFa(x);
    int faY = findFa(y);
    if (faX != faY)
        fa[faX] = faY;
}
// 存所有边双
vector<int> e_bcc[MAXN + 5];
void dfs(int u, int eId)
{
    vis[u] = true;
    visE[eId] = true;
    low[u] = dfn[u] = ++idx;
    for (int i = 0; i < edge[u].size(); i++)
    {
        int v = edge[u][i].first;     // u->v;
        int uvId = edge[u][i].second; // u->v;
        if (!vis[v])
        {
            dfs(v, uvId);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
            {
                // u->v 是桥
                // cout << u << "x" << v << endl;
            }
            else
            {
                merge(u, v);
                // cout << u << "~" << v << endl;
            }
        }
        else if (!visE[uvId])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(make_pair(v, i));
        edge[v].push_back(make_pair(u, i));
    }
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            idx = 0;
            dfs(i, 0);
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int faI = findFa(i);
        if (e_bcc[faI].empty())
            cnt++;
        e_bcc[faI].push_back(i);
    }
    cout << cnt << "\n";
    for (int i = 1; i <= n; i++)
    {
        if (!e_bcc[i].empty())
        {
            cout << e_bcc[i].size() << " ";
            for (int x : e_bcc[i])
                cout << x << " ";
            cout << "\n";
        }
    }
    return 0;
}

0

33DAI 33 LV 6 (1/1) SU @ 2023-6-6 13:38:26

P1656 炸铁路

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 150;
int n, m;
vector<int> edge[MAXN + 5]; // edge[i]：与i相连的点
bool vis[MAXN + 5];         // vis[i]: i有没有走过；
int fa[MAXN + 5];           // fa[i]：i 的父节点
bool flag[MAXN + 5];        // flag[i]：fa[i]~i 是否为桥
int low[MAXN + 5];          // low[i]：不经过父节点能走到的最小时间戳；
int dfn[MAXN];              // dfn[i]：深搜生成树的时间戳
int idx, resCnt;            // idx：时间戳； resCnt：割点数量
vector<pair<int, int>> ans;
void dfs(int u, int father)
{
    vis[u] = true;
    low[u] = dfn[u] = ++idx;
    fa[u] = father;
    for (int i = 0; i < edge[u].size(); i++)
    {
        int v = edge[u][i]; // u->v;
        if (!vis[v])
        {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])
            {
                ans.push_back(make_pair(min(u, v), max(u, v)));
                flag[v] = true;
            }
        }
        else if (v != father)
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            idx = 0;
            dfs(i, i);
        }
    }
    sort(ans.begin(), ans.end());
    for (auto x : ans)
        cout << x.first << " " << x.second << "\n";
    return 0;
}

0

33DAI 33 LV 6 (1/1) SU @ 2023-6-6 13:08:21

P3388 【模板】割点（割顶）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n, m;
vector<int> edge[MAXN + 5];         // edge[i]：与i相连的点
bool vis[MAXN + 5], flag[MAXN + 5]; // vis[i]: i有没有走过；flag[i]：i是否为割点
int low[MAXN + 5];                  // low[i]：不经过父节点能走到的最小时间戳；
int dfn[MAXN];                      // dfn[i]：深搜生成树的时间戳
int idx, resCnt;                    // idx：时间戳； resCnt：割点数量
void dfs(int u, int fa)
{
    vis[u] = true;
    low[u] = dfn[u] = ++idx;
    int childCnt = 0;
    for (int i = 0; i < edge[u].size(); i++)
    {
        int v = edge[u][i]; // u->v;
        if (!vis[v])
        {
            childCnt++;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (u != fa && low[v] >= dfn[u] && !flag[u])
            {
                resCnt++;
                flag[u] = true;
            }
        }
        else
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (u == fa && childCnt >= 2 && !flag[u])
    {
        resCnt++;
        flag[u] = true;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            idx = 0;
            dfs(i, i);
        }
    }
    cout << resCnt << endl;
    for (int i = 1; i <= n; i++)
        if (flag[i])
            cout << i << " ";
    return 0;
}

0

33DAI 33 LV 6 (1/1) SU @ 2023-6-6 11:29:59

P3443 [POI2006]LIS-The Postman

代码写得很乱，以后有空修缮一下

#include <bits/stdc++.h>
using namespace std;
// 存图
const int MAXN = 400000;
const int MAXM = 800000;
int n, m, t;
// 初始的边
int uu[MAXM + 5], vv[MAXM + 5];
// 初始的边 ee[起点][终点] = 边的编号
map<int, int> ee[MAXN + 5];
// 必要路径的边的前驱后继
int pre[MAXM + 5], nxt[MAXM + 5];
// 当前边作为必要路径链的起点时的对应终点
int fnl[MAXM + 5];
// 存所有的压缩边：<压缩后的边,压缩路径的第一条的编号>
multimap<pair<int, int>, int> spe;
// 当前必要路径的每条边的ID
int nowPath[MAXM + 5];
bool pathFlag[MAXM + 5];
// 欧拉路相关
// pair 为 <边的终点,边的编号>
vector<pair<int, int>> e[MAXN + 5];
// 每个点的入度/出度
int inD[MAXN + 5], outD[MAXN + 5];
// 每个点已经搞定了几条边
int cnt[MAXN + 5];
// 最终路径
stack<int> ans;
vector<int> path;
void dfs(int u)
{
    while (cnt[u] < e[u].size())
    {
        int v = e[u][cnt[u]].first;
        int eId = e[u][cnt[u]].second;
        cnt[u]++;
        dfs(v);
    }
    ans.push(u);
}
// 判断图是否连通
int fa[MAXN + 5];
set<int> points; // 新图的点的编号
int findFa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findFa(fa[x]);
}
void merge(int x, int y)
{
    int faX = findFa(x);
    int faY = findFa(y);
    if (faX != faY)
        fa[faX] = faY;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //  输入
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> uu[i] >> vv[i];
        ee[uu[i]][vv[i]] = i;
        outD[uu[i]]++;
        inD[vv[i]]++;
    }
    // 判断初始图是否有回路
    for (int i = 1; i <= n; i++)
        if (inD[i] != outD[i])
        {
            cout << "NIE\n";
            return 0;
        }
    cin >> t;
    while (t--)
    {
        int len, last, now, eId;
        cin >> len;
        // 合并要求的路径，构建每条边的前驱后继
        cin >> last;
        for (int i = 2; i <= len; i++)
        {
            cin >> now;
            eId = ee[last][now];
            nowPath[i] = eId;
            // last->now 检查是否存在这条边
            if (eId == 0)
            {
                cout << "NIE\n";
                return 0;
            }
            // nowPath[i-1] -> eId;
            // 检查边是否有多个前驱后继
            if (i > 2 && (pre[eId] != 0 && pre[eId] != nowPath[i - 1] ||
                          nxt[nowPath[i - 1]] != 0 && nxt[nowPath[i - 1]] != eId))
            {
                cout << "NIE\n";
                return 0;
            }
            // 连接前驱后继
            if (i > 2)
            {
                pre[nowPath[i]] = nowPath[i - 1];
                nxt[nowPath[i - 1]] = nowPath[i];
            }
            last = now;
        }
        // 检查当前路径是否有重边
        for (int i = 2; i <= len; i++)
            pathFlag[nowPath[i]] = false;
        for (int i = 2; i <= len; i++)
            if (pathFlag[nowPath[i]] == true)
            {
                cout << "NIE\n";
                return 0;
            }
            else
            {
                pathFlag[nowPath[i]] = true;
            }
    }
    // 构建要求的路径
    for (int i = 1; i <= m; i++)
    {
        int eId = i;
        if (pre[eId] == 0 && nxt[eId] != 0)
        {
            while (nxt[eId] != 0)
                eId = nxt[eId];
            fnl[i] = vv[eId];
            spe.insert(make_pair(make_pair(uu[i], fnl[i]), i));
        }
    }
    // 构建新图
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++)
    {
        if (pre[i] != 0)
            continue;
        int u = uu[i], v = vv[i];
        if (nxt[i] != 0)
            v = fnl[i];
        e[u].push_back(make_pair(v, i));
        points.insert(u);
        points.insert(v);
        merge(u, v);
        // 计算入度出度
        outD[u]++;
        inD[v]++;
    }
    // 检查新图能不能从1号点开始走
    if (e[1].empty())
    {
        cout << "NIE\n";
        return 0;
    }
    // 检查新图有没有欧拉回路
    for (int i = 1; i <= n; i++)
    {
        if (inD[i] != outD[i])
        {
            cout << "NIE\n";
            return 0;
        }
    }
    // 检查新图是否连通
    for (auto i : points)
    {
        if (findFa(i) != findFa(*(points.begin())))
        {
            cout << "NIE\n";
            return 0;
        }
    }
    dfs(1);
    // 解压
    path.push_back(ans.top());
    int last = ans.top();
    ans.pop();
    while (!ans.empty())
    {
        int now = ans.top();
        ans.pop();
        auto it = spe.find(make_pair(last, now));
        if (it == spe.end())
            path.push_back(now);
        else
        {
            int eId = it->second;
            path.push_back(vv[eId]);
            while (nxt[eId] != 0)
            {
                eId = nxt[eId];
                path.push_back(vv[eId]);
            }
            spe.erase(it);
        }
        last = now;
    }
    // 检查并输出
    if (path.size() == m + 1)
    {
        cout << "TAK\n";
        for (auto x : path)
            cout << x << "\n";
    }
    else
    {
        cout << "NIE\n";
    }
    return 0;
}

0

33DAI 33 LV 6 (1/1) SU @ 2023-6-5 23:56:11

P2731 [USACO3.3]骑马修栅栏 Riding the Fences

#include <bits/stdc++.h>
using namespace std;
// 存图
const int MAXN = 500;
const int MAXM = 2048;
int n, m;
// pair 为 <边的终点,边的编号>
vector<pair<int, int>> e[MAXN + 5];
// 每个点的度
int d[MAXN + 5];
// 欧拉路的起点终点
int st, ed;
// 每条边还在不在
bool vis[MAXM + 5];
// 最终路径
stack<int> ans;
void dfs(int u)
{
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].first;
        int eId = e[u][i].second;
        if (vis[eId])
            continue;
        if (eId <= m)
        {
            vis[eId] = true;
            vis[eId + m] = true;
        }
        else
        {
            vis[eId] = true;
            vis[eId - m] = true;
        }
        dfs(v);
    }
    ans.push(u);
}
bool pFlag[MAXN + 5];
vector<int> points;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //  输入
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        pFlag[u] = pFlag[v] = true;
        e[u].push_back(make_pair(v, i));
        e[v].push_back(make_pair(u, i + m));
        // 计算入度出度
        d[u]++;
        d[v]++;
    }
    for (int i = 1; i <= MAXN; i++)
        if (pFlag[i])
            points.push_back(i);
    // 如果题目未保证弱连通，那么需要先判断一下
    // 找欧拉路的起点终点
    st = ed = 0;
    for (int i : points)
    {
        if (d[i] % 2 != 0)
        {
            if (st == 0)
                st = i;
            else if (ed == 0)
                ed = i;
            else
            {
                cout << "No\n";
                return 0;
            }
        }
    }
    if (st != 0 && ed == 0)
    {
        cout << "No\n";
        return 0;
    }
    if (st == 0 && ed == 0)
        st = ed = points[0];
    if (st > ed)
        swap(st, ed);
    // 题目要求按字典序最小的欧拉路，排个序
    for (int i : points)
        sort(e[i].begin(), e[i].end());
    dfs(st);
    while (!ans.empty())
    {
        cout << ans.top() << "\n";
        ans.pop();
    }
    cout << "\n";
    return 0;
}

0

33DAI 33 LV 6 (1/1) SU @ 2023-6-5 23:21:14

P7771 【模板】欧拉路径

#include <bits/stdc++.h>
using namespace std;
// 存图
const int MAXN = 100000;
const int MAXM = 200000;
int n, m;
// 存图
vector<int> e[MAXN + 5];
// 每个点的入度/出度
int inD[MAXN + 5], outD[MAXN + 5];
// 欧拉路的起点终点
int st, ed;
// 每个点已经搞定了几条边
int cnt[MAXN + 5];
// 每条边还在不在
bool vis[MAXM + 5];
// 最终路径
stack<int> ans;
void dfs(int u)
{
    while (cnt[u] < e[u].size())
    {
        int v = e[u][cnt[u]];
        cnt[u]++;
        dfs(v);
    }
    ans.push(u);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        // 计算入度出度
        outD[u]++;
        inD[v]++;
    }
    // 如果题目未保证弱连通，那么需要先判断一下
    // 找欧拉路的起点终点
    int cntD = 0;      // 出度入度不相等的点的数量
    bool flag = false; // 是否存在出入度相差大于1的点
    st = ed = 0;
    for (int i = 1; i <= n; i++)
    {
        if (inD[i] != outD[i])
        {
            cntD++;
            if (abs(inD[i] - outD[i]) > 1)
                flag = true;
            if (inD[i] + 1 == outD[i])
                st = i;
            if (outD[i] + 1 == inD[i])
                ed = i;
        }
    }
    // 判断是否存在欧拉路
    if ((cntD != 2 && cntD != 0) ||
        flag ||
        (cntD == 2 && (!st || !ed)))
    {
        cout << "No\n";
        return 0;
    }
    if (cntD == 0)
        st = ed = 1;
    // 题目要求按字典序最小的欧拉路，排个序
    for (int i = 1; i <= n; i++)
        sort(e[i].begin(), e[i].end());
    dfs(st);
    while (!ans.empty())
    {
        cout << ans.top() << " ";
        ans.pop();
    }
    cout << "\n";
    return 0;
}

11 条题解

CF1213F Unstable String Sort

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

P4306 [JSOI2010]连通数

Floyd 传递闭包

缩点后拓扑排序dp

TLE

AC

缩点后记忆化搜索dp

P3387 【模板】缩点

P8435 【模板】点双连通分量

P8436 【模板】边双连通分量

P1656 炸铁路

P3388 【模板】割点（割顶）

P3443 [POI2006]LIS-The Postman

P2731 [USACO3.3]骑马修栅栏 Riding the Fences

P7771 【模板】欧拉路径

扩展题单 - 连通性相关

信息

11 条题解

Floyd 传递闭包

缩点后拓扑排序dp

TLE

AC

缩点后记忆化搜索dp

扩展题单 - 连通性相关

信息

还没有账户？

登录