Pagini recente » Cod sursa (job #3216612) | Cod sursa (job #1589928) | Cod sursa (job #276535) | Cod sursa (job #2005475) | Cod sursa (job #937117)
Cod sursa(job #937117)
#include<fstream>
#include<vector>
#include<stack>
#define MAX_N 100
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
stack<int> s,where;
int n,m,x,y,nr;
void dfs(vector<int>adj[], vector<int> &visited, int node, stack<int> &s)
{
visited[node]=1;
for(unsigned int i=0;i<adj[node].size();i++)
if(visited[adj[node][i]]==0)
dfs(adj, visited, adj[node][i],s);
s.push(node);
}
vector<int> from_where;
int main()
{
f>>n>>m;
vector<int> adj[n+1],adj_inv[n+1];
vector<int> visited1(n+1,0), visited2(n+1,0);
for(int i=1;i<=m;i++)
{
f>>x>>y;
adj[x].push_back(y);
adj_inv[y].push_back(x);
}
dfs(adj, visited1,1,s);
while(!s.empty())
{
x = s.top();
if(visited2[x]==0)
{
nr++;
from_where.push_back(x);
dfs(adj_inv, visited2, x, where);
}
s.pop();
}
g<<nr<<'\n';
from_where.pop_back();
while(!from_where.empty())
{
while(where.top()!=from_where.back())
{
g<<where.top()<<" ";
where.pop();
}
g<<'\n';
from_where.pop_back();
}
while(!where.empty())
{
g<<where.top()<<" ";
where.pop();
}
return 0;
}