Pagini recente » Cod sursa (job #322715) | Cod sursa (job #2403047) | Cod sursa (job #1754627) | Cod sursa (job #2465878) | Cod sursa (job #717010)
Cod sursa(job #717010)
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define PB push_back
#define maxN 100005
int N , M , marked[maxN];
int pls[maxN] , mns[maxN];
vector <int> lista[maxN] , trans[maxN];
queue <int> Q;
void BFS (vector <int> graf[maxN] , int viz[maxN] , int start , int line)
{
Q.push (start);
viz[start] = line;
while (!Q.empty ())
{
int nod = Q.front ();
Q.pop ();
for (unsigned int i = 0 ; i < graf[nod].size () ; ++i)
{
int nodcur = graf[nod][i];
if (viz[nodcur] == line)
continue;
viz[nodcur] = line;
Q.push (nodcur);
}
}
}
int main ()
{
ifstream f ("ctc.in");
ofstream g ("ctc.out");
f >> N >> M;
int a , b;
for (int i = 1 ; i <= M ; ++i)
{
f >> a >> b;
lista[a].PB (b);
trans[b].PB (a);
}
int line = 0 , start;
for (int i = 1 ; i <= N ; ++i)
if (!marked[i])
{
start = i;
++line;
BFS (lista , pls , start , line);
BFS (trans , mns , start , line);
for (int i = 1 ; i <= N ; ++i)
if (pls[i] == mns[i] && pls[i] != 0)
marked[i] = pls[i];
}
g << line << "\n";
for (int i = 1 ; i <= line ; ++i)
{
for (int j = 1 ; j <= N ; ++j)
if (marked[j] == i)
g << j << " ";
g << "\n";
}
return 0;
}