Pagini recente » Cod sursa (job #2246667) | Cod sursa (job #331119) | Cod sursa (job #2328762) | Cod sursa (job #2735260) | Cod sursa (job #950931)
Cod sursa(job #950931)
#include <stdio.h>
#include <vector>
#include <stack>
#define Nmax 100001
using namespace std;
vector<int> G[Nmax],GT[Nmax];
int viz[Nmax],N,M;
stack<int> st;
vector<int> comp;
vector< vector<int> > sol;
void read_data()
{
FILE*f = fopen("ctc.in","r");
fscanf(f,"%d%d",&N,&M);
int x,y;
while(M--)
{
fscanf(f,"%d%d",&x,&y);
G[x].push_back(y);
GT[y].push_back(x);
}
fclose(f);
}
void dfs_one(int node)
{
viz[node] = 1;
for(vector<int>::iterator it = G[node].begin();it!=G[node].end();++it)
if(viz[*it] == 0)
dfs_one(*it);
st.push(node);
}
void dfs_two(int node)
{
viz[node] = -1;
for(vector<int>::iterator it = GT[node].begin();it!=GT[node].end();++it)
if(viz[*it] != -1)
dfs_two(*it);
comp.push_back(node);
}
void solve()
{
for(int i=1;i<=N;++i)
if(!viz[i])
dfs_one(i);
int elem;
while(!st.empty())
{
elem = st.top();st.pop();
if(viz[elem] != -1)
{
dfs_two(elem);
sol.push_back(comp);
comp.clear();
}
}
}
void write_data()
{
FILE*g = fopen("ctc.out","w");
fprintf(g,"%d\n", sol.size());
for(int i = 0, size = sol.size() ; i < size ; ++i)
{
for(vector< int >::iterator it = sol[i].begin();it!=sol[i].end();++it)
fprintf(g,"%d ", *it);
fprintf(g,"\n");
}
fclose(g);
}
int main()
{
read_data();
solve();
write_data();
return 0;
}