Pagini recente » Cod sursa (job #407217) | Istoria paginii runda/eusebiuoji2016cls9/clasament | Cod sursa (job #821537) | Cod sursa (job #1416400) | Cod sursa (job #953710)
Cod sursa(job #953710)
using namespace std;
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100003
ifstream in("ctc.in");
ofstream out("ctc.out");
int N,M;
vector <int> graph[NMAX],tgraph[NMAX],comp;
vector < vector<int> > sol;
stack <int> S;
int viz1[NMAX],viz2[NMAX];//,all_visited=false,removed[NMAX];
void dfs(int node)
{
vector<int>::iterator it;
viz1[node]=1;
for (it=graph[node].begin();it!=graph[node].end();it++)
if (viz1[*it]==0) dfs(*it);
S.push(node);
}
void dfst(int node)
{
vector<int>::iterator it;
comp.push_back(node);
viz2[node]=1;
for (it=tgraph[node].begin();it!=tgraph[node].end();it++)
{ if (viz2[*it]==0)
dfst(*it);
}
}
int main()
{
int x,y,i;
in>>N>>M;
for (i=1;i<=N;i++) {viz1[i]=viz2[i]=0;}
for (i=1;i<=M;i++)
{
in>>x>>y;
graph[x].push_back(y);
tgraph[y].push_back(x);
}
for (i=1;i<=N;i++)
if (viz1[i]==0) dfs(i);
while (!S.empty())
{
x=S.top();S.pop();
if (viz2[x]==0)
{
dfst(x);
sol.push_back(comp);
comp.clear();
}
}
vector<int>::iterator it;
out<<sol.size()<<"\n";
for(i=0;i<sol.size();i++)
{
for(it=sol[i].begin();it!=sol[i].end();it++)
out<<*it<<" ";
out<<"\n";
}
return 0;
}