Pagini recente » Cod sursa (job #2443447) | Cod sursa (job #2904569) | Cod sursa (job #190761) | Cod sursa (job #1860779) | Cod sursa (job #902558)
Cod sursa(job #902558)
// Include
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
// Definitii
#define pb push_back
// Constante
const int sz = (int)1e5+1;
// Functii
void dfs(int node);
void reversedDFS(int node);
// Variabile
ifstream in("ctc.in");
ofstream out("ctc.out");
bool found;
int nodes, edges;
bool visited[sz];
vector<int> graph[sz], reversedGraph[sz];
stack<int> st;
vector< vector<int> > answer;
vector<int> answerTemp;
// Main
int main()
{
in >> nodes >> edges;
int rFrom, rTo;
while(edges--)
{
in >> rFrom >> rTo;
graph[rFrom].pb(rTo);
reversedGraph[rTo].pb(rFrom);
}
for(int i=1 ; i<=nodes ; ++i)
dfs(i);
while(!st.empty())
{
found = false;
reversedDFS(st.top());
if(found)
{
answer.pb(answerTemp);
answerTemp.clear();
}
st.pop();
}
out << answer.size() << '\n';
vector< vector<int> >::iterator answerIT, answerEND=answer.end();
for(answerIT=answer.begin() ; answerIT!=answerEND ; ++answerIT)
{
vector<int>::iterator it, end=answerIT->end();
for(it=answerIT->begin() ; it!=end ; ++it)
out << *it << ' ';
out << '\n';
}
in.close();
out.close();
return 0;
}
void dfs(int node)
{
if(visited[node])
return;
visited[node] = true;
vector<int>::iterator it, end=graph[node].end();
for(it=graph[node].begin() ; it!=end ; ++it)
dfs(*it);
st.push(node);
}
void reversedDFS(int node)
{
if(!visited[node])
return;
visited[node] = false;
answerTemp.pb(node);
found = true;
vector<int>::iterator it, end=reversedGraph[node].end();
for(it=reversedGraph[node].begin() ; it!=end ; ++it)
reversedDFS(*it);
}