Pagini recente » Cod sursa (job #370877) | Cod sursa (job #1238442) | Cod sursa (job #2570470) | Cod sursa (job #64752) | Cod sursa (job #1424418)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define MAX_DIM 50005
std::vector <int> L[MAX_DIM];
std::vector <int> Lt[MAX_DIM];
std::vector <int> T;
int color[MAX_DIM];
std::vector <int> componente[MAX_DIM];
int nr_c = 0;
ifstream inFile("sortaret.in");
ofstream outFile("ctc.out");
void explor(int node)
{
color[node] = 1;
for(unsigned int i = 0; i < L[node].size(); i++) {
int k = L[node][i];
if( color[k] == 0 ) explor(k);
}
T.push_back(node);
}
void explor1(int node)
{
componente[nr_c].push_back(node);
color[node] = 1;
for(unsigned int i = 0; i < Lt[node].size(); i++) {
int k = Lt[node][i];
if( color[k] == 0 ) explor1(k);
}
}
int main()
{
int n, m;
inFile >> n >> m;
int x, y;
for(int i = 1; i <= m; i++) {
inFile >> x >> y;
L[x].push_back(y);
Lt[y].push_back(x);
}
for(int node = 1; node <= n; node++) {
if( color[node] == 0 ) explor(node);
}
for(unsigned int i = 0; i <= (T.size() - 1)/2; i++) {
swap(T[i], T[T.size() - 1 - i]);
}
for(int i = 1; i <= n; i++) color[i] = 0;
for(int i = 0; i < T.size(); i++) {
int k = T[i];
if(color[k] == 0) {explor1(k); nr_c++; }
}
outFile << nr_c << "\n";
for(int i = 0; i < nr_c; i++) {
for(int j = 0; j < componente[i].size(); j++)
outFile << componente[i][j] << " ";
outFile << "\n";
}
}