#define NDEBUG // NDEBUG definita nella versione che consegno #include #include #include #include using namespace std; const int DIM = 1000; int m; int n; int p; long long int S[DIM+2][DIM+2][2]; long long int maxCFC = 1; set seenCFC; int main() { #ifdef NDEBUG ifstream fin("input.txt"); assert( fin ); ofstream fout("output.txt"); #else istream &fin(cin); ostream &fout(cout); #endif fin >> m; fin >> n; fin >> p; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { S[i][j][0] = 0; } } for (int i = 1; i <= p; ++i) { int xp; int yp; fin >> xp; fin >> yp; S[xp][yp][0] = 1; S[xp][yp][1] = maxCFC++; } // Calcola le componenti fortemente connesse eseguendo una DFS. // Metti i nodi in coda (stante la struttura della scacchiera basta visitarli // in ordine) e per ogni nodo uscente imposta la stessa CFC. for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { // Controlla i nodi a destra e in alto if (S[i + 1][j + 1][0] == 1) { S[i + 1][j + 1][1] = S[i][j][1]; } } } // Conta le componenti connesse. for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (S[i][j][0] == 1) { seenCFC.insert(S[i][j][1]); } } } fout << seenCFC.size() << endl; return 0; }