Pagini recente » Cod sursa (job #1525597) | Cod sursa (job #3230694) | Cod sursa (job #2121474) | Cod sursa (job #203081) | Cod sursa (job #2979242)
#include <fstream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, a[2][200005], start[100005], a1[2][200005], start1[100005], nr, p[100005], mi[100005], viz[100005];
void df1(int nod);
void df2(int nod);
void plusminus();
int main()
{
int i, x, y;
fin >> n >> m;
for (i = 1; i <= m; i++) {
fin >> x >> y;
a[0][i] = y;
a[1][i] = start[x];
start[x] = i;
a1[0][i] = x;
a1[1][i] = start1[y];
start1[y] = i;
}
plusminus();
fout << nr << "\n";
return 0;
}
void df1(int nod)
{
int x;
p[nod] = nr;
x = start[nod];
while (x) {
if (p[a[0][x]] != nr)
df1(a[0][x]);
x = a[1][x];
}
}
void df2(int nod)
{
int x;
mi[nod] = nr;
x = start1[nod];
while (x) {
if (mi[a1[0][x]] != nr)
df2(a1[0][x]);
x = a1[1][x];
}
}
void plusminus()
{
int i, j;
for (i = 1; i <= n; i++)
if (viz[i] == 0) {
viz[i] = nr;
nr++;
df1(i);
df2(i);
for (j = 1; j <= n; j++)
if (p[j] == nr && mi[j] == nr)
viz[j] = nr;
}
}