Pagini recente » Cod sursa (job #2574884) | Rating Dumitrache Eduard Ionut (edydumy) | Cod sursa (job #3042186) | Cod sursa (job #1491073) | Cod sursa (job #451414)
Cod sursa(job #451414)
#include<fstream>
#include<vector>
#include<list>
#define IN "dfs.in"
#define OUT "dfs.out"
#define INF ~(1<<31)
#define NIL -1
#define ALB 0
#define GRI 1
#define NEGRU 2
using namespace std;
vector<list<int> >L;
int N, M;
vector <int> P;
vector <int> REZ;
vector <int> C, S, F;
int t, nr;
void read (char *);
void DFS ();
void DFSV (int);
int main(int argc, char **argv)
{
read (argv[1]);
DFS();
int i;
FILE *fout = fopen (OUT, "w");
fprintf (fout, "%d\n", nr);
fclose (fout);
return 0;
}
void read (char *filename)
{
FILE *fin = fopen (IN, "r");
int i;
fscanf(fin, "%d%d", &N, &M);
L.resize(N+1);
for (i = 0; i < M; ++i)
{
int from, to;
fscanf (fin, "%d%d", &from, &to);
L[from].push_back(to);
L[to].push_back(from);
}
fclose (fin);
}
void DFS ()
{
C.resize (N+1);
P.resize (N+1);
S.resize (N+1);
F.resize (N+1);
int i;
for (i = 1; i <= N; ++i)
P[i] = NIL;
for (i = 1 ; i <= N; ++i)
if (C[i] == ALB)
{
nr++;
DFSV (i);
}
}
void DFSV (int s)
{
REZ.push_back(s);
C[s] = GRI;
S[s] = ++t;
list<int>::iterator i;
for (i = L[s].begin(); i != L[s].end(); ++i)
if (C[*i] == ALB)
{
P[*i] = s;
DFSV (*i);
}
C[s] = NEGRU;
F[s] = ++t;
}