Pagini recente » Cod sursa (job #2557637) | Cod sursa (job #410698) | Cod sursa (job #1439867) | Cod sursa (job #269699) | Cod sursa (job #948534)
Cod sursa(job #948534)
#include "iostream"
#include "fstream"
#include "vector"
#include "stack"
using namespace std;
#define NMAX 100005
ifstream inf("ctc.in");
ofstream outf("ctc.out");
int nr_nod;
bool vizitat[NMAX];
int count;
stack<int> S;
vector<int> sol[NMAX], in[NMAX], out[NMAX];
void Read()
{
int x, y, muchii;
inf >> nr_nod >> muchii;
for (int i = 0; i < muchii; ++ i)
{
inf >> x >> y;
in[x].push_back(y);
out[y].push_back(x);
}
}
void Print()
{
outf << count << '\n';
vector <int> ::iterator it;
for(int i = 1; i <= count; ++i)
{
for(it = sol[i].begin(); it != sol[i].end(); ++ it)
outf << *it << " ";
outf << '\n';
}
}
void Dff(int start)
{
vizitat[start] = true;
vector <int>::iterator it;
for(it = in[start].begin(); it != in[start].end(); ++it)
if(vizitat[*it] == 0)
Dff(*it);
S.push(start);
}
void Dfs(int start)
{
vizitat[start] = false;
sol[count].push_back(start);
vector <int>::iterator it;
for(it = out[start].begin(); it != out[start].end(); ++ it)
if(vizitat[*it] == true)
Dfs(*it);
}
void Kosaraju()
{
for(int i = 1; i <= nr_nod; ++ i)
if(vizitat[i] == false)
Dff(i);
while(!S.empty()) {
if(vizitat[S.top()] == true)
{
count ++;
Dfs(S.top());
}
S.pop();
}
}
int main()
{
Read();
Kosaraju();
Print();
return 0;
}