Pagini recente » Cod sursa (job #1544338) | Cod sursa (job #2482850) | Cod sursa (job #194426) | Cod sursa (job #1654751) | Cod sursa (job #1098168)
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
FILE *in,*out;
//Constante
const int sz = (int)1e5+1;
//Definitii
#define pb push_back
//Functii
void dfs(int node);
void backDFS(int node);
//Variabile
int nodes, edges;
bool visited[sz], inStack[sz];
vector <int> graph[sz], reversedGraph[sz];
stack <int> stacky;
vector < vector<int> > answer;
vector <int> temp;
//Main
int main()
{
in = fopen("ctc.in","rt");
out = fopen("ctc.out","wt");
fscanf(in,"%d%d", &nodes, &edges);
for(int i=1; i<=edges; ++i)
{
int from, to;
fscanf(in,"%d%d", &from, &to);
graph[from].pb(to);
reversedGraph[to].pb(from);
}
for(int i=1; i<=nodes; ++i)
{
if(!inStack[i])
dfs(i);
}
while(!stacky.empty())
{
int current = stacky.top();
stacky.pop();
if(inStack[current])
{
backDFS(current);
answer.pb(temp);
temp.clear();
}
}
fprintf(out,"%d\n", answer.size());
vector < vector<int> >::iterator it, end = answer.end();
for(it = answer.begin(); it!=end; ++it)
{
vector<int>::iterator vit, vend = it->end();
for(vit = it->begin(); vit!=vend; ++vit)
fprintf(out,"%d ", *vit);
fprintf(out,"\n");
}
fclose(in);
fclose(out);
return 0;
}
void dfs(int node)
{
visited[node] = true;
vector<int>::iterator it, end = graph[node].end();
for(it = graph[node].begin(); it!=end; ++it)
if(!visited[*it])
dfs(*it);
stacky.push(node);
inStack[node] = true;
}
void backDFS(int node)
{
inStack[node] = false;
temp.pb(node);
vector<int>::iterator it, end = reversedGraph[node].end();
for(it = reversedGraph[node].begin(); it!=end; ++it)
if(inStack[*it])
backDFS(*it);
}