timus 1080 - Map coloring solution

timus 1080 - Map coloring statement: http://acm.timus.ru/problem.aspx?space=1&num=1080

timus 1080 - Map coloring solution: http://ideone.com/vNEv5A

//http://ideone.com/vNEv5A
//169445
#include <iostream>
#include <cstdio>
using namespace std;

int n, adj[105][105]={0}, c[105], a;

bool dfs(int v, int col) {
    if(c[v]!=-1 && c[v]==col) return true;
    else if(c[v]!=-1 && c[v]!=col) return false;
    c[v]=col;
    for(int i=0; i<n; i++) if(adj[v][i] && !dfs(i, 1-col)) return false;
    return true;
}

int main() {
    scanf("%d", &n);
    for(int i=0; i<n; i++) while(true) {
        scanf("%d", &a);
        if(a==0) break;
        adj[i][a-1]=adj[a-1][i]=1;
    }
    for(int i=0; i<105; i++) c[i]=-1;
    if(dfs(0, 0)==true) for(int i=0; i<n; i++) printf("%d", c[i]);
    else printf("-1");
    return 0;
}

note: the code is almost the same of irancoldfusion's: https://bitbucket.org/pykello/timus/src/a3037a3bd7a7/1080.cpp

timus 1106 - Two Teams solution

timus 1106 - Two Teams statement: http://acm.timus.ru/problem.aspx?space=1&num=1106

timus 1106 - Two Teams solution: http://ideone.com/r8JprM

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int adj[105][105]={0}, b[105]={0}, g[105]={0}, f, cnt, flag=0, n;
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        cnt=0;
        while(true) {
            scanf("%d", &f);
            if(f==0 && cnt==0) {flag=1; break;}
            else if(f==0) break;
            adj[i][f-1]=1, cnt++;
        }
    }
    cnt=0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(adj[i][j]==1 && b[j]==0) {
                b[i]=b[j]=1;
                if(g[i]==1) g[j]=2;
                else g[j]=1, cnt++;
            }
        }
    }
    if(flag==1) printf("0");
    else {
        printf("%d\n", cnt);
        for(int i=0; i<n; i++) if(g[i]==1) printf("%d ", i+1);
    }
    return 0;
}

note: dfs or bfs, i dont know which applies to solve this question. but in my case, it was like this: assign this guy to one of either groups, and assign its friends(if not assigned yet) to opposing group. adj[] array is adjacency list(you would have seen that while you were studying bfs). b[] is for bool, whether that vertex has been visited or not. g[] for group.

for other versions of solutions:
1 - https://github.com/marioyc/Online-Judge-Solutions/blob/master/Timus%20Online%20Judge/1106%20-%20Two%20Teams.cpp

2 - https://github.com/galymzhan/plzgosolve/blob/master/timus/1106.cpp

3 - http://blog.csdn.net/pegasuswang_/article/details/12394355

4 - https://code.google.com/p/morbidel-timus/source/browse/trunk/done/1106.cpp?r=15