Pagini recente » Cod sursa (job #52795) | Cod sursa (job #2385034) | Cod sursa (job #2213604) | Cod sursa (job #1990908) | Cod sursa (job #2199386)
//+-
#include <fstream>
#include <vector>
#include <stack>
#define Nmax 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> v1[Nmax], v2[Nmax], v3[Nmax];
int seen[Nmax];
stack <int> st;
int n, m;
int num_ctc=0;
vector <int> ::iterator it;
void first_Dfs(int node)
{
seen[node]=1;
for ( int i = 0, l = v1[node].size(); i < l ; i ++ )
{ int nnode=v1[node][i];
if( seen[nnode] != 0) continue;
first_Dfs(nnode);
}
st.push(node);
}
void second_Dfs(int node)
{
seen[node]=-1;
for ( int i = 0, l = v2[node].size(); i < l ; i ++ )
{
int nnode=v2[node][i];
if(seen[nnode]==-1) continue;
second_Dfs(nnode);
}
v3[num_ctc].push_back(node);
}
int main()
{ int x, y;f >> n >> m ;
while ( m -- )
{
f >> x >> y;
v1[x].push_back(y);
v2[y].push_back(x);
}
for ( int i = 1 ; i <= n ; i ++ )
if(!seen[i])
first_Dfs(i);
while(!st.empty())
{
if(seen[st.top()] == -1 )
{
st.pop();
continue;
}
num_ctc++;
second_Dfs(st.top());
st.pop();
}
g << num_ctc << '\n';
for ( int i = 1 ; i <= num_ctc ; i ++ )
{
for ( it=v3[i].begin() ; it != v3[i].end() ; it ++ )
g << *it << " ";
g << '\n';
}
return 0;
}