Pagini recente » Cod sursa (job #2808589) | Cod sursa (job #934957) | Cod sursa (job #592572) | Cod sursa (job #1977429) | Cod sursa (job #874336)
Cod sursa(job #874336)
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
//Constante
const int sz = (int)1e5+1;
//Functii
void dfs(int node);
void printDFS(int node);
FILE *in,*out;
int nodes, edges;
bool visited[sz];
bool inStack[sz];
vector <int> graph[sz], reversedGraph[sz];
stack <int> st;
vector< vector<int> > answer;
vector<int> answerTemp;
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 rFrom, rTo;
fscanf(in,"%d%d",&rFrom,&rTo);
graph[rFrom].push_back(rTo);
reversedGraph[rTo].push_back(rFrom);
}
for(int i=1; i<=nodes; ++i)
if(!inStack[i])
dfs(i);
while(!st.empty())
{
int current = st.top();
st.pop();
if(inStack[current])
{
printDFS(current);
answer.push_back(answerTemp);
answerTemp.clear();
}
}
fprintf(out,"%d\n",answer.size());
vector< vector<int> >::iterator vit, vend = answer.end();
for(vit=answer.begin(); vit!=vend; ++vit)
{
vector<int>::iterator it, end = vit->end();
for(it=vit->begin(); it!=end; ++it)
fprintf(out,"%d ",*it);
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);
st.push(node);
inStack[node] = true;
}
void printDFS(int node)
{
inStack[node] = false;
answerTemp.push_back(node);
vector<int>::iterator it, end = reversedGraph[node].end();
for(it=reversedGraph[node].begin(); it!=end; ++it)
if(inStack[*it])
printDFS(*it);
}