Coloring Edges – Educational CodeForces Round 72 (Rated for Div. 2)

The meaning of the question: https://codeforc.es/contest/1217/problem/D

Give you a directed graph, which requires no edges of the same color in a loop, ask How do you dye it in at least a few colors?

Thinking:

If there is no ring, it is all 1; if there is a ring, the small to large side is 1, and the large to small side is 2.

 1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);

 2 #include //sprintf islower isupper

 3 #include //malloc exit strcat itoa system("cls")

 4 #include //pair

 5 #include //freopen("C:\Users\13606\Desktop\draft.txt","r",stdin);

 6 #include 

 7 //#include 

 8 //#include

 9 #include 

 10 #include 

 11 #include <set>

 12 #include <string.h>//strstr substr

 13 #include <string>

 14 #include //srand(((unsigned)time(NULL))); Seed n=rand()%10-0~9;

 15 #include 

 16 #include 

 17 #include //priority_queue, greater> q;//less

 18 #include //emplace_back

 19 //#include 

 20 //#include //reverse(a, a+len);// ~! ~! floor

 21 #include //sort + unique: sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)

 22 using  namespace std;//next_permutation(a+1,a+1+n); //prev_permutation

 23 #define fo(a,b,c) for(register int a=b;a<=c;++a)

 24 #define fr(a,b,c) for(register int a=b;a>=c;--a)

 25 #define mem(a,b) memset(a,b ,sizeof(a))

 26 #define pr printf

 27 #define sc scanf

 28 #define ls rt<<1

 29 #define rs rt<<1|1

 30 typedef long long ll;

 31 void swapp(int &a,int &b);

 32 double fabss(double a);

 33 int maxx(int a,int b);

 34 int minn(int a,int b);

 35 int Del_bit_1(int n);

 36 int lowbit(int n);

 37 int abss(int a);

 38 //const long long INF=(1LL<<60);

 39 const  double E=2.718281828;

 40 const double PI=acos(-1.0);

 41 const int inf=(1<<30);

 42 const double ESP=1e-9;

 43 const int mod=(int)1e9+7;

 44 const int N=(int)1e6+10;

 45

 46 int  in[N];

 47 vectorint> > G(N);

 48

 49 bool top_sort(int n)

 50 {

 51 int cont=0;

 52 queue<int> q;

 53 for(int i=1;i<=n;i++)

 54 if(in[i]==0)

 55  q.push(i);

 56 while(!q.empty())

 57  {

 58 int x=q.front();

 59  q.pop();

 60 cont++;

 61 for(int i=0;i)

 62  {

 63 in[G[x][i] ]--;

 64 if(in[G[x][i]]==0 )

 65  q.push(G[x][i]);

 66 }

 67 }

 68 return (cont==n);

 69 }

 70 struct node

 71 {

 72 int u,v;

 73 }edge[N];

 74

 75 int main()

 76 {

 77 int n,m;

 78 sc("%d%d",&n,&m);

 79 for(int i=1;i<=m;++i )

 80  {

 81 int u,v;

 82 sc("%d%d",&u,&v);

 83 edge[i]={u,v};

 84 in[v]++;

 85  G[u].push_back(v);

 86 }

 87 if(top_sort(n))

 88  {

 89 pr("1
");

 90 for(int i=1;i<=m;++i )

 91 pr("1 ");

 92 }

 93 else

 94  {

 95 pr("2
");

 96 for(int i=1;i<=m;++i )

 97 pr("%d ",edge[i].u>edge[i].v?1:2);

 98 }

 99 return 0;

100 }

101

102 /************************************************** ************************************/

103

104 int maxx(int a,int b)

105 {

106 return a>b?a:b;

107 }

108

109 void swapp(int &a,int &b)

110 {

111 a^=b^=a^=b;

112 }

113

114 int lowbit(int n)

115 {

116 return n&(-n);

117 }

118

119 int Del_bit_1(int n)

120 {

121 return n&(n-1);

122 }

123

124 int abss(int a)

125 {

126 return a>0?a:-a;

127 }

128

129 double fabss(double a)

130 {

131 return a>0?a:-a;

132 }

133

134 int minn(int a,int b)

135 {

136 return aa:b;

137 }

 1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);

 2 #include //sprintf islower isupper

 3 #include //malloc exit strcat itoa system("cls")

 4 #include //pair

 5 #include //freopen("C:\Users\13606\Desktop\draft.txt","r",stdin);

 6 #include 

 7 //#include 

 8 //#include

 9 #include 

 10 #include 

 11 #include <set>

 12 #include <string.h>//strstr substr

 13 #include <string>

 14 #include //srand(((unsigned)time(NULL))); Seed n=rand()%10-0~9;

 15 #include 

 16 #include 

 17 #include //priority_queue, greater> q;//less

 18 #include //emplace_back

 19 //#include 

 20 //#include //reverse(a, a+len);// ~! ~! floor

 21 #include //sort + unique: sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)

 22 using  namespace std;//next_permutation(a+1,a+1+n); //prev_permutation

 23 #define fo(a,b,c) for(register int a=b;a<=c;++a)

 24 #define fr(a,b,c) for(register int a=b;a>=c;--a)

 25 #define mem(a,b) memset(a,b ,sizeof(a))

 26 #define pr printf

 27 #define sc scanf

 28 #define ls rt<<1

 29 #define rs rt<<1|1

 30 typedef long long ll;

 31 void swapp(int &a,int &b);

 32 double fabss(double a);

 33 int maxx(int a,int b);

 34 int minn(int a,int b);

 35 int Del_bit_1(int n);

 36 int lowbit(int n);

 37 int abss(int a);

 38 //const long long INF=(1LL<<60);

 39 const  double E=2.718281828;

 40 const double PI=acos(-1.0);

 41 const int inf=(1<<30);

 42 const double ESP=1e-9;

 43 const int mod=(int)1e9+7;

 44 const int N=(int)1e6+10;

 45

 46 int  in[N];

 47 vectorint> > G(N);

 48

 49 bool top_sort(int n)

 50 {

 51 int cont=0;

 52 queue<int> q;

 53 for(int i=1;i<=n;i++)

 54 if(in[i]==0)

 55  q.push(i);

 56 while(!q.empty())

 57  {

 58 int x=q.front();

 59  q.pop();

 60 cont++;

 61 for(int i=0;i)

 62  {

 63 in[G[x][i] ]--;

 64 if(in[G[x][i]]==0 )

 65  q.push(G[x][i]);

 66 }

 67 }

 68 return (cont==n);

 69 }

 70 struct node

 71 {

 72 int u,v;

 73 }edge[N];

 74

 75 int main()

 76 {

 77 int n,m;

 78 sc("%d%d",&n,&m);

 79 for(int i=1;i<=m;++i )

 80  {

 81 int u,v;

 82 sc("%d%d",&u,&v);

 83 edge[i]={u,v};

 84 in[v]++;

 85  G[u].push_back(v);

 86 }

 87 if(top_sort(n))

 88  {

 89 pr("1
");

 90 for(int i=1;i<=m;++i )

 91 pr("1 ");

 92 }

 93 else

 94  {

 95 pr("2
");

 96 for(int i=1;i<=m;++i )

 97 pr("%d ",edge[i].u>edge[i].v?1:2);

 98 }

 99 return 0;

100 }

101

102 /************************************************** ************************************/

103

104 int maxx(int a,int b)

105 {

106 return a>b?a:b;

107 }

108

109 void swapp(int &a,int &b)

110 {

111 a^=b^=a^=b;

112 }

113

114 int lowbit(int n)

115 {

116 return n&(-n);

117 }

118

119 int Del_bit_1(int n)

120 {

121 return n&(n-1);

122 }

123

124 int abss(int a)

125 {

126 return a>0?a:-a;

127 }

128

129 double fabss(double a)

130 {

131 return a>0?a:-a;

132 }

133

134 int minn(int a,int b)

135 {

136 return aa:b;

137 }