#include <stdio.h>
int main(void) {
printf("Enter the number of states : "); int n;
int set1[n],set2[n],f,q[n][2];//for Equivalents
for(int i=0;i<n;i++){
}
printf("\n\nEnter the number of Final states : "); int final[f];
for(int i=0;i<f;i++){
}
/*for(int r=0;r<n;r++){
printf("\nq[%d][0]=%d",r,q[r][0]);
printf("\nq[%d][1]=%d",r,q[r][1]);
}*/
int flag=0,temp[n],t=0,cont=0;
for(int i=0;i<n;i++){
flag=0;
cont=0;
for(int k=0; k<n;k++){
if(i==temp[k]){
cont=1;
}
}
if(cont==1){
continue;
}
for(int j=0;j<n;j++){
if(i==q[j][0] || i==q[j][1]){
flag=1;
break;
}
}
if(flag==0){
temp[t]=i;
t++;
q[i][0]=-1;
q[i][1]=-1;
set1[i]=-1;
set2[i]=-1;
i=-1;
}
}
printf("\n\nRemoved unreachable states :-"); t=0;
for(int r=0;r<n;r++){
if(q[r][0]!=-1){
printf("\nq[%d][0]=%d",r
,q
[r
][0]); printf("\nq[%d][1]=%d",r
,q
[r
][1]); if(r==final[t]){
set1[r]=1;
if(t<f){
t++;
}
}else{
set1[r]=0;
}
}
}
/*for(int i=0;i<n;i++){
if(set1[i]!=-1){
printf("\nset1[%d]=%d",i,set1[i]);
printf("\nset2[%d]=%d",i,set2[i]);
}
}*/
/*flag=0;
//exit=0;
t=2;cont=0;
set2[0]=0;
int x=0,y1,z1,z2,y2;
int j=0,i=0;
for(i=1;i<n;n++){
x=set1[i];
if(x<0){
continue;
}
flag=0;
for(j=0;j<i;j++){
if(set1[j]<0)continue;
if(x==set1[j]){
y1=q[i][0];
z1=q[j][0];
y2=q[i][1];
z2=q[j][1];
if(set1[y1]==set1[z1] && set1[y2]==set1[z2]){
set2[i]=set2[j];
flag=1;
break;
}
}
}
if(flag==0){
t++;
cont++;
set2[j]=cont;
}
}*/
/*set2[0]=0;
set2[1]=0;
set2[3]=0;
set2[5]=0;
int a=0,b=0,x1=0,x2=0,y1=0,y2=0;
for(a=1;a<n;a++){
flag=0;
if(set1[a]==-1){
printf("\n skiped a %d",a
continue;
}else{
for(b=0;b<a;b++){
if(set1[b]==-1){
printf("\n skiped b %d",b);
}else{
if(set1[a]==set1[b]){
x1=q[a][0];
x2=q[b][0];
y1=q[a][1];
y2=q[b][1];
if(set1[x1]==set1[x2] && set1[y1]==set1[y2]){
set2[a]=set2[b];
flag=1;
break;
}
}
}
}
if(flag==0){
t++;
set2[a]=t;
}
}
}*/
set2[0]=0;
int a=0,b=0,x1=0,x2=0,y1=0,y2=0;
for(a=1;a<n;a++){
flag=0;
if(set1[a]!=-1){
for(b=0;b<a;b++){
if(set1[b]!=-1){
if(set1[a]==-1 || set1[b]==-1){
}
if(set1[a]==set1[b]){
x1=q[a][0];
x2=q[b][0];
y1=q[a][1];
y2=q[b][1];
if(set1[x1]==set1[x2] && set1[y1]==set1[y2]){
set2[a]=set2[b];
flag=1;
break;
}
}
}else{
}
}
if(flag==0){
t++;
set2[a]=t;
}
}else{
}
}
for(int i=0;i<n;i++){
if(set1[i]!=-2){
// printf("\nset1[%d]=%d",i,set1[i]);
printf("\nset2[%d]=%d",i
,set2
[i
]); }
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgbWFpbih2b2lkKSB7CiAgIAoJcHJpbnRmKCJFbnRlciB0aGUgbnVtYmVyIG9mIHN0YXRlcyA6ICIpOwoJaW50IG47CglzY2FuZigiJWQiLCZuKTsKCWludCBzZXQxW25dLHNldDJbbl0sZixxW25dWzJdOy8vZm9yIEVxdWl2YWxlbnRzCglmb3IoaW50IGk9MDtpPG47aSsrKXsKCSAgICBwcmludGYoIlxucVslZF1bMF0gPSAiLGkpOwoJICAgIHNjYW5mKCIlZCIsJnFbaV1bMF0pOwoJICAgIHByaW50ZigiXG5xWyVkXVsxXSA9ICIsaSk7CgkgICAgc2NhbmYoIiVkIiwmcVtpXVsxXSk7Cgl9CglwcmludGYoIlxuXG5FbnRlciB0aGUgbnVtYmVyIG9mIEZpbmFsIHN0YXRlcyA6ICIpOwoJc2NhbmYoIiVkIiwmZik7CglpbnQgZmluYWxbZl07Cglmb3IoaW50IGk9MDtpPGY7aSsrKXsKCSAgICBwcmludGYoIlxuRmluYWwgU3RhdGVzIDogIik7CgkgICAgc2NhbmYoIiVkIiwmZmluYWxbaV0pOwoJfQoJCgkvKmZvcihpbnQgcj0wO3I8bjtyKyspewoJICAgIHByaW50ZigiXG5xWyVkXVswXT0lZCIscixxW3JdWzBdKTsKCSAgICBwcmludGYoIlxucVslZF1bMV09JWQiLHIscVtyXVsxXSk7Cgl9Ki8KCQoJaW50IGZsYWc9MCx0ZW1wW25dLHQ9MCxjb250PTA7Cglmb3IoaW50IGk9MDtpPG47aSsrKXsKCSAgICBmbGFnPTA7CgkgICAgY29udD0wOwoJICAgIGZvcihpbnQgaz0wOyBrPG47aysrKXsKCSAgICAgICAgaWYoaT09dGVtcFtrXSl7CgkgICAgICAgICAgICBjb250PTE7CgkgICAgICAgIH0KCSAgICB9CgkgICAgaWYoY29udD09MSl7CgkgICAgICAgIGNvbnRpbnVlOwoJICAgIH0KCSAgICBmb3IoaW50IGo9MDtqPG47aisrKXsKCSAgICAgICAgaWYoaT09cVtqXVswXSB8fCBpPT1xW2pdWzFdKXsKCSAgICAgICAgICAgIGZsYWc9MTsKCSAgICAgICAgICAgIGJyZWFrOwoJICAgICAgICB9CgkgICAgfQoJICAgIGlmKGZsYWc9PTApewoJICAgICAgICB0ZW1wW3RdPWk7CgkgICAgICAgIHQrKzsKCSAgICAgICAgcVtpXVswXT0tMTsKCSAgICAgICAgcVtpXVsxXT0tMTsKCSAgICAgICAgc2V0MVtpXT0tMTsKCSAgICAgICAgc2V0MltpXT0tMTsKCSAgICAgICAgaT0tMTsKCSAgICB9Cgl9CglwcmludGYoIlxuXG5SZW1vdmVkIHVucmVhY2hhYmxlIHN0YXRlcyA6LSIpOwoJdD0wOwoJZm9yKGludCByPTA7cjxuO3IrKyl7CgkgICAgaWYocVtyXVswXSE9LTEpewoJICAgICAgICBwcmludGYoIlxucVslZF1bMF09JWQiLHIscVtyXVswXSk7CgkgICAgICAgIHByaW50ZigiXG5xWyVkXVsxXT0lZCIscixxW3JdWzFdKTsKCSAgICAgICAgaWYocj09ZmluYWxbdF0pewoJICAgICAgICAgICAgc2V0MVtyXT0xOwoJICAgICAgICAgICAgaWYodDxmKXsKCSAgICAgICAgICAgICAgICB0Kys7CgkgICAgICAgICAgICB9CgkgICAgICAgIH1lbHNlewoJICAgICAgICAgICAgc2V0MVtyXT0wOwoJICAgICAgICB9CgkgICAgfQoJfQoJLypmb3IoaW50IGk9MDtpPG47aSsrKXsKCSAgICBpZihzZXQxW2ldIT0tMSl7CgkgICAgICAgIHByaW50ZigiXG5zZXQxWyVkXT0lZCIsaSxzZXQxW2ldKTsKCSAgICAgICAgcHJpbnRmKCJcbnNldDJbJWRdPSVkIixpLHNldDJbaV0pOwoJICAgIH0KCX0qLwoJCgkvKmZsYWc9MDsKCS8vZXhpdD0wOwogICAgdD0yO2NvbnQ9MDsKICAgIHNldDJbMF09MDsKICAgIGludCB4PTAseTEsejEsejIseTI7CiAgICBpbnQgaj0wLGk9MDsKICAgIGZvcihpPTE7aTxuO24rKyl7CiAgICAgICAgeD1zZXQxW2ldOwogICAgICAgIGlmKHg8MCl7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KICAgICAgICBmbGFnPTA7CiAgICAgICAgZm9yKGo9MDtqPGk7aisrKXsKICAgICAgICAgICAgaWYoc2V0MVtqXTwwKWNvbnRpbnVlOwogICAgICAgICAgICBpZih4PT1zZXQxW2pdKXsKICAgICAgICAgICAgICAgIHkxPXFbaV1bMF07CiAgICAgICAgICAgICAgICB6MT1xW2pdWzBdOwogICAgICAgICAgICAgICAgeTI9cVtpXVsxXTsKICAgICAgICAgICAgICAgIHoyPXFbal1bMV07CiAgICAgICAgICAgICAgICBpZihzZXQxW3kxXT09c2V0MVt6MV0gJiYgc2V0MVt5Ml09PXNldDFbejJdKXsKICAgICAgICAgICAgICAgICAgICBzZXQyW2ldPXNldDJbal07CiAgICAgICAgICAgICAgICAgICAgZmxhZz0xOwogICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGlmKGZsYWc9PTApewogICAgICAgICAgICB0Kys7CiAgICAgICAgICAgIGNvbnQrKzsKICAgICAgICAgICAgc2V0MltqXT1jb250OwogICAgICAgIH0KICAgIH0qLwogICAgCiAgICAvKnNldDJbMF09MDsKICAgIHNldDJbMV09MDsKICAgIHNldDJbM109MDsKICAgIHNldDJbNV09MDsKICAgIGludCBhPTAsYj0wLHgxPTAseDI9MCx5MT0wLHkyPTA7CiAgICBmb3IoYT0xO2E8bjthKyspewogICAgICAgIGZsYWc9MDsKICAgICAgICBpZihzZXQxW2FdPT0tMSl7CiAgICAgICAgICAgIHByaW50ZigiXG4gc2tpcGVkIGEgJWQiLGEKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfWVsc2V7CiAgICAgICAgICAgIAogICAgICAgIGZvcihiPTA7YjxhO2IrKyl7CiAgICAgICAgICAgIGlmKHNldDFbYl09PS0xKXsKICAgICAgICAgICAgICAgIHByaW50ZigiXG4gc2tpcGVkIGIgJWQiLGIpOwogICAgICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgaWYoc2V0MVthXT09c2V0MVtiXSl7CiAgICAgICAgICAgICAgICB4MT1xW2FdWzBdOwogICAgICAgICAgICAgICAgeDI9cVtiXVswXTsKICAgICAgICAgICAgICAgIHkxPXFbYV1bMV07CiAgICAgICAgICAgICAgICB5Mj1xW2JdWzFdOwogICAgICAgICAgICAgICAgaWYoc2V0MVt4MV09PXNldDFbeDJdICYmIHNldDFbeTFdPT1zZXQxW3kyXSl7CiAgICAgICAgICAgICAgICAgICAgc2V0MlthXT1zZXQyW2JdOwogICAgICAgICAgICAgICAgICAgIGZsYWc9MTsKICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICB9CiAgICAgICAgaWYoZmxhZz09MCl7CiAgICAgICAgICAgIHQrKzsKICAgICAgICAgICAgc2V0MlthXT10OwogICAgICAgIH0KICAgICAgICB9CiAgICB9Ki8KICAgIAogICAgc2V0MlswXT0wOwogICAgaW50IGE9MCxiPTAseDE9MCx4Mj0wLHkxPTAseTI9MDsKICAgIGZvcihhPTE7YTxuO2ErKyl7CiAgICAgICAgZmxhZz0wOwogICAgICAgIGlmKHNldDFbYV0hPS0xKXsKICAgICAgICAgICAgZm9yKGI9MDtiPGE7YisrKXsKICAgICAgICAgICAgICAgIGlmKHNldDFbYl0hPS0xKXsKICAgICAgICAgICAgICAgICAgICBpZihzZXQxW2FdPT0tMSB8fCBzZXQxW2JdPT0tMSl7CiAgICAgICAgICAgICAgICAgICAgICAgICBwcmludGYoIlxuSGVsbG8iKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgaWYoc2V0MVthXT09c2V0MVtiXSl7CiAgICAgICAgICAgICAgICAgICAgICAgIHgxPXFbYV1bMF07CiAgICAgICAgICAgICAgICAgICAgICAgIHgyPXFbYl1bMF07CiAgICAgICAgICAgICAgICAgICAgICAgIHkxPXFbYV1bMV07CiAgICAgICAgICAgICAgICAgICAgICAgIHkyPXFbYl1bMV07CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKHNldDFbeDFdPT1zZXQxW3gyXSAmJiBzZXQxW3kxXT09c2V0MVt5Ml0pewogICAgICAgICAgICAgICAgICAgICAgICAgICAgc2V0MlthXT1zZXQyW2JdOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgZmxhZz0xOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgICAgICAgICBwcmludGYoIlxuU0tJUEVEIGI9JWQiLGIpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKGZsYWc9PTApewogICAgICAgICAgICAgICAgdCsrOwogICAgICAgICAgICAgICAgc2V0MlthXT10OwogICAgICAgICAgICB9CiAgICAgICAgfWVsc2V7CiAgICAgICAgICAgIHByaW50ZigiXG5TS0lQRUQgYT0lZCIsYSk7CiAgICAgICAgfQogICAgfQoJCmZvcihpbnQgaT0wO2k8bjtpKyspewoJICAgIGlmKHNldDFbaV0hPS0yKXsKCSAgICAgICAvLyBwcmludGYoIlxuc2V0MVslZF09JWQiLGksc2V0MVtpXSk7CgkgICAgICAgIHByaW50ZigiXG5zZXQyWyVkXT0lZCIsaSxzZXQyW2ldKTsKCSAgICB9Cgl9CgkKCQoJCglyZXR1cm4gMDsKfQoK