題意
https://vjudge.net/problem/CodeForces-1217D
請給一個有向圖著色，使得沒有一個環只有一個顏色，您需要最小化使用顏色的數量，
思路
因為是有向圖，每個環兩個顏色就可以滿足了，所以最大為2，最小為1，
法1 dfs：
用dfs判斷有向圖的環，每次把構成環的最后那條邊染成2，其余染成1，
法2 拓撲排序：
容易發現，對于一個有向圖，如果成環那么點的序號必不是單調的，因為最后的那個點又會連回起始點，
所以我們把u<v染成1，u>v染成2，然后拓撲排序判環，如果有環那么就輸出染色方案，否則全輸出1，
代碼
法1：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=5e3+5;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
vector<int> g[N];
int e[N][N],vis[N],col[N],gg,in[N];
void dfs(int u)
{
int sz=g[u].size();
in[u]=1;
for(int i=0;i<sz;i++)
{
int v=g[u][i];
if(!vis[v])
{
vis[v]=1;
col[e[u][v]]=1;
dfs(v);
}
else if(in[v])
{
col[e[u][v]]=2;
gg=1;
}
else
{
col[e[u][v]]=1;
}
}
in[u]=0;
}
int main()
{
std::ios::sync_with_stdio(false);
int n,m;
while(cin>>n>>m)
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
e[u][v]=i;
}
gg=0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
// col[i]=1;
vis[i]=1;
dfs(i);
}
}
if(!gg)
{
cout<<1<<endl;
for(int i=1;i<=m;i++)
cout<<1<<" ";
cout<<endl;
}
else
{
cout<<2<<endl;
for(int i=1;i<=m;i++)
cout<<col[i]<<" ";
cout<<endl;
}
}
return 0;
}
法2：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
vector<int> g[N];
int col[N],du[N];
int n,m;
bool topo()
{
queue<int> q;
for(int i=1; i<=n; i++)
if(du[i]==0) q.push(i);
int cnt=0;
while(!q.empty())
{
int t=q.front();
for(int i:g[t])
{
du[i]--;
if(du[i]==0)
q.push(i);
}
cnt++;
q.pop();
}
if(cnt!=n)
return false;
return true;
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1; i<=m; i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
col[i]=(u<v);
du[v]++;
}
if(topo())
{
cout<<1<<endl;
for(int i=1;i<=m;i++)
cout<<1<<" ";
cout<<endl;
}
else
{
cout<<2<<endl;
for(int i=1;i<=m;i++)
cout<<col[i]+1<<" ";
cout<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/119223.html
標籤：其他
上一篇：Kibana的使用
下一篇：CSDN之星投票 謝謝幫忙投票